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

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

示例 1：

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

示例 2：

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

提示：

树中节点的数量在 [0, 10(4)] 区间内。

-100 <= Node.val <= 100

分别递归左右子树，取最大值即可

或者用层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        queue<TreeNode *> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            int nums = q.size();
            while (nums--) {
                TreeNode *cur = q.front();
                q.pop();
                if (cur->left)
                    q.push(cur->left);
                if (cur->right)
                    q.push(cur->right);
            }
            ans++;
        }
        return ans;
    }
};