二叉树的最大深度

描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

非递归：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

// 用队列
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0; // 如果根节点为空，则直接返回
        queue<TreeNode*> q; // 定义队列，初始值为根节点
        q.push(root);
        int depth = 0; // 定义最大深度
        while(!q.empty()){
            int n = q.size();
            depth++; // 每层加一
            for(int i=0; i<n; i++){
                auto t = q.front();
                q.pop();
                if (t->left != nullptr) q.push(t->left); // 将左子节点加入到队列中
                if (t->right != nullptr) q.push(t->right); // 将右子节点加入到队列中
            }
        }
        return depth;
    }
};

// 用栈
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        stack<pair<TreeNode*, int>> s; // 使用一个pair来记录每个节点以及它们的深度
        int max_depth = 0; // 记录最大深度的值
        s.push(make_pair(root, 1)); // 将根节点入栈，深度为1
        while (!s.empty()) { // 栈不为空时
            auto node = s.top().first; // 取出栈顶节点
            int depth = s.top().second; // 取出栈顶节点的深度
            s.pop(); // 将节点出栈
            max_depth = max(max_depth, depth); // 更新最大深度的值
            if (node->left != NULL) { // 如果节点有左子节点，将左子节点入栈，深度加1
                s.push(make_pair(node->left, depth + 1));
            }
            if (node->right != NULL) { // 如果节点有右子节点，将右子节点入栈，深度加1
                s.push(make_pair(node->right, depth + 1));
            }
        }
        return max_depth; // 返回最大深度的值
    }
};

递归：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 如果根节点为空，则返回0
        if (root == NULL) {
            return 0;
        }
        // 递归计算左子树和右子树的深度
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        // 返回左子树和右子树深度的最大值加1，即为整棵树的深度
        return max(leftDepth, rightDepth) + 1;
    }
};

Python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth = 0
        q = [root]
        while q:
            n = len(q)
            depth += 1
            for i in range(n):
                node = q.pop(0)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return depth