二叉树的最大深度

1
class Solution {
2
public:
3
    int getdepth(TreeNode* node){
4
        // 开始前先判断节点是否为空
5
        // 注意：此处不能写 node == null，编译器会报错，在 C++ 里该使用 nullptr
6
        if (node == nullptr) return 0;
7

8
        // 将左右子树都挨个“递”过去
9
        int leftdepth = getdepth(node->left);
10
        int rightdepth = getdepth(node->right);
11

12
        // 记录下子树最大深度，然后 +1。max() 是库函数，目的是找到最大值
13
        int depth = 1 + max(leftdepth, rightdepth);
14
        return depth;
15
    }
16

17
    int maxDepth(TreeNode* root) {
18
        return getdepth(root);
19
    }
20
};

1
#include <queue>
2

3
class Solution {
4
public:
5
    int maxDepth(TreeNode* root) {
6
        if (!root) return 0;
7
        queue<TreeNode*> q;
8
        q.push(root);
9
        int depth = 0;
10

11
        while (!q.empty()) {
12
            int size = q.size();    // 1. 获取当前层的节点个数（快照）
13
            for (int i = 0; i < size; ++i) {
14
                TreeNode* node = q.front();
15
                q.pop();
16
                if (node->left)  q.push(node->left);
17
                if (node->right) q.push(node->right);
18
            }
19
            depth++;                // 2. 一层扫完深度加 1
20
        }
21
        return depth;
22
    }
23
};