二叉树的最大深度 图解题解

最大深度数的是节点还是边

题目定义的深度是「从根到最远叶子这条路径上的节点个数」：空树深度 0，只有一个根的树深度 1。这个口径要先钉死——如果按边数理解，单根树会算成 0，整个答案系统性地差 1。输入是一棵普通二叉树，输出一个整数。

为什么求树的深度自然想到递归

直接想「根到最远叶子有多远」不好下手，因为最远的叶子可能藏在任何一支里。换个问法就豁然开朗：整棵树的深度，跟它两棵子树的深度是什么关系？答案是——树的最深路径必然从根出发、走进左右子树之一，所以整棵树的深度 = 两棵子树深度的较大者再加上根自己这一层，即 max(left, right) + 1。

这一步把「算一棵大树」拆成了「算两棵小树」这两个一模一样的子问题，而子问题还能继续往下拆，直到空节点——空树没有任何节点，深度定为 0，这就是递归出口。整个解法就是把这条关系式原样写成代码。

为什么是后序遍历而不是前序

关系式 max(left, right) + 1 里，父节点的答案依赖两个孩子的答案：不先知道左右子树各有多深，就不知道该给谁加一。所以计算顺序必须是「先左子树、再右子树、最后自己」，这正是后序遍历的定义。落到执行上，递归会一路扎到最底层，叶子的深度最先确定（左右都是空，max(0,0)+1 = 1），然后一层层往上回传，每上一层取较大值加一，回到根时得到的就是整棵树的最大深度。

这个递归为什么一定算得对

正确性可以用归纳法一句话说清：空树深度 0 显然正确；假设左右子树的递归结果都对，那么根到最远叶子的路径必定经过较深的那棵子树，长度就是那棵子树的深度加上根这一个节点——恰好是 max(left, right) + 1。底层对、每一步组合也对，整体就对。这也是大多数二叉树递归题共同的论证套路：只要「出口正确 + 组合关系正确」，就不必担心中间过程。

复杂度与最容易写错的边界

时间 O(n)：每个节点恰好被访问一次，每次只做一次比较和一次加法。空间 O(h)：递归栈最深等于树高 h，平衡树约 O(log n)，退化成链时 O(n)。

两个高频错误：一是递归出口把空节点深度写成 1——出口是整个递归的地基，写 1 会让所有答案多 1；二是把深度当成边数返回 max(left, right) 而忘了 +1，那个 +1 代表的是当前节点自己，漏掉答案就永远是 0。

Java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;        // 空节点深度 0（出口）
        int left  = maxDepth(root.left);   // 后序：先算左
        int right = maxDepth(root.right);  // 再算右
        return Math.max(left, right) + 1;  // 较深子树 + 1
    }
}

Python

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:                    # 空节点深度 0
            return 0
        left = self.maxDepth(root.left)     # 后序：先算左
        right = self.maxDepth(root.right)   # 再算右
        return max(left, right) + 1         # 较深子树 + 1

C++

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;      // 空节点深度 0
        int left  = maxDepth(root->left);   // 后序：先算左
        int right = maxDepth(root->right);  // 再算右
        return max(left, right) + 1;        // 较深子树 + 1
    }
};