https://leetcode.cn/problems/maximum-depth-of-binary-tree/

题面

给定一个二叉树 root ，返回其最大深度。

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

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

1
2
输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

代码

递归写法

1
2
3
4
5
6
7
8
9
10
int getdepth(TreeNode* node) {
    if (node == NULL) return 0;
    int leftdepth = getdepth(node->left);
    int rightdepth = getdepth(node->right);
    int depth = 1 + max(leftdepth, rightdepth);
    return depth;
}
int maxdepth(TreeNode* root) {
    return getdepth(root);
}

迭代写法

使用层序遍历最合适，因为最大深度就是二叉树的层数，和层序遍历的方式极其吻合。这种写法更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    queue<TreeNode*> que;
    que.push(root);
    int depth = 0;
    while (!que.empty()) {
        depth++; // 记录深度
        int size = que.size(); // 一定要存size，因为que.size()会变
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
    }
    return depth;
}