二叉树的最大深度

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

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

示例 1：

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

示例 2：

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

提示：

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

解法一（递归 DFS）：

/**
 * 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;
        }

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return max(leftDepth, rightDepth) + 1;
    }
};

解法二（迭代层序遍历）：

/**
 * 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 size = q.size();
            depth++;

            for (int i = 0; i < size; i++)
            {
                TreeNode* node = q.front();
                q.pop();

                if (node->left != nullptr)
                {
                    q.push(node->left);
                }

                if (node->right != nullptr)
                {
                    q.push(node->right);
                }
            }
        }	

        return depth;
    }
};

核心思想

一棵二叉树的最大深度，可以看成：

根节点 + 左右子树中较大的最大深度

如果当前节点为空，它没有任何节点，深度是 0。

如果当前节点不为空，那么从当前节点向下的最长路径，一定来自左子树或右子树中较深的那一边。

因此递推关系是：

maxDepth(root) = max(maxDepth(root->left), maxDepth(root->right)) + 1

这题最关键的观察是：

当前节点的最大深度，只依赖左右子树的最大深度。

所以递归可以直接按照树的结构计算答案。

如果不使用递归，也可以按层遍历整棵树。遍历完一层，深度就增加 1，最后遍历的层数就是最大深度。

解法一：递归 DFS

递归函数 maxDepth(root) 表示以 root 为根的子树最大深度。

当 root == nullptr 时：

return 0;

当 root 不为空时，分别求左右子树的最大深度：

int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);

当前节点本身占一层，所以返回：

return max(leftDepth, rightDepth) + 1;

解法二：迭代层序遍历

层序遍历使用队列保存当前还没有处理的节点。

队列中的节点按层排列：

先放入第 1 层节点，再放入第 2 层节点，再放入第 3 层节点

每次循环处理当前队列中的所有节点，这些节点正好属于同一层。

先记录当前层的节点数：

int size = q.size();

然后处理这 size 个节点，并把它们的非空左右孩子加入队列。

当前层处理完成后，深度增加 1：

depth++;

当队列为空时，说明整棵树的所有层都已经处理完，depth 就是最大深度。

为什么层数等于最大深度

层序遍历从根节点开始：

• 根节点属于第 1 层
• 根节点的孩子属于第 2 层
• 孩子的孩子属于第 3 层

因此，最远叶子节点所在的层数，就是根节点到它的路径上的节点数。

而最远叶子节点所在的层，也就是整棵树的最大层数。

所以层序遍历的层数正好等于二叉树的最大深度。

边界情况

如果二叉树为空：

root = []

递归解法直接返回 0。

迭代解法中队列不会开始遍历，也返回 0。

如果树只有一个根节点：

root = [1]

最大深度是 1。

如果树退化成一条链，最大深度就是链上节点的数量。

如果树是一棵完全平衡的树，递归和层序遍历都会正确取到最深的叶子层。

正确性证明

我们证明：两个解法都能正确返回二叉树的最大深度。

结论 1：空树的最大深度是 0

空树不包含任何节点，也不存在从根节点到叶子节点的路径。

因此空树最大深度为 0。

两个解法都对 root == nullptr 返回 0，所以边界处理正确。

结论 2：递归公式正确计算当前子树的最大深度

对于非空节点 root，从它出发的最长路径只能经过左子树或右子树。

左子树能提供的最长路径长度是 leftDepth，右子树能提供的最长路径长度是 rightDepth。

取两者较大值，再加上当前根节点这一层，得到：

max(leftDepth, rightDepth) + 1

这个值既不会超过真实最大深度，也不会遗漏更深的路径。

因此递归解法正确。

结论 3：层序遍历每处理一轮，恰好完成一层

开始处理一轮时，队列中保存的正是当前层的所有节点。

变量 size 记录当前层节点数量。

循环只处理这 size 个节点，因此不会把下一层节点误算到当前层。

处理当前节点时，把它的非空孩子加入队列，而这些孩子全部属于下一层。

所以一轮循环恰好对应树的一层。

结论 4：层序遍历得到的层数就是最大深度

根节点所在层数为 1，每向下一层，根到节点的路径就多一个节点。

因此最深叶子所在的层数，就是根到最远叶子的最长路径节点数。

层序遍历会依次处理所有层，并且每处理一层就让 depth 增加 1。

所以最终的 depth 就是二叉树的最大深度。

得出结论

由结论 1 和结论 2 可知，递归 DFS 解法正确。

由结论 3 和结论 4 可知，迭代层序遍历解法正确。

因此两个解法都能返回二叉树的最大深度。

举例理解

以：

root = [3,9,20,null,null,15,7]

为例，这棵树可以表示为：

      3
     / \
    9  20
      /  \
     15   7

层序遍历过程如下：

处理完第 3 层后，队列为空。

所以最大深度是：

3

复杂度分析

设二叉树节点数为 n，树的高度为 h。

解法一

每个节点都会被递归访问一次。

• 时间复杂度：O(n)
• 空间复杂度：O(h)

空间复杂度来自递归调用栈。

解法二

每个节点入队一次、出队一次。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

队列在最宽的一层可能保存 O(n) 个节点。

如果树比较深，递归解法的额外空间更小；如果不想使用递归，层序遍历更直观。