1.题目介绍

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

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

示例 1：

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

示例 2：

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

提示：

树中节点的数量在 \([0, 10^{4}]\) 区间内。
\(-100 <= Node.val <= 100\)

2.题解

2.1 方法一：深度优先搜索

思路：递归

代码

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

2.2 方法二：广度优先搜索

思路

用队列存储一层所有节点的信息，在进入下一层时，将其一一出队，检测是否有左右子树，同时使用标记变量记录层数。
若有，说明下一层存在，同时将该节点入队，作为下一层检测时的树节点；
若无，说明下一层不存在，当前层数为最大层数，退出循环。

代码

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 sz = Q.size();
            while(sz > 0){
                TreeNode *temp = Q.front(); Q.pop();
                if (temp->left) Q.push(temp->left);
                if (temp->right) Q.push(temp->right);
                sz--;
            }
            ans++;
        } 
        return ans;
    }
};