题目描述
思路解析
一句话答案：LeetCode 104 二叉树的最大深度用后序递归几行解决：空节点深度为 0，非空节点深度 = max(左子树深度, 右子树深度) + 1。必须先算完左右孩子才能算自己，所以是后序遍历的形状。每个节点访问一次，时间 O(n)，递归栈空间 O(h)。
最大深度数的是节点还是边
题目定义的深度是「从根到最远叶子这条路径上的节点个数」：空树深度 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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
节点深度描述它离根有多远；这里返回的是以该节点为根的子树高度，不是节点自身的深度。
准备 · 整棵树：根节点值为三。接下来先访问子树，再将子树高度返回给父调用；所有节点保持原来的位置。
访问节点 3：进入节点 3 的调用。父调用暂时保留，先递归计算左右子树，当前高度还不能返回。
访问节点 9：进入节点 9 的调用。父调用暂时保留，先递归计算左右子树，当前高度还不能返回。
访问节点 4：进入节点 4 的调用。父调用暂时保留，先递归计算左右子树，当前高度还不能返回。
访问节点 2 · 叶子：节点 2 是叶子，左右子树均为空。两个子调用返回零后，本节点将返回一。
回传 2 · 子树高度 = 1：节点 2 收到左右子树高度 0 和 0，取较大值再加一，返回 1。
访问节点 1 · 叶子：节点 1 是叶子，左右子树均为空。两个子调用返回零后，本节点将返回一。
回传 1 · 子树高度 = 1：节点 1 收到左右子树高度 0 和 0，取较大值再加一，返回 1。
回传 4 · 子树高度 = 2：节点 4 收到左右子树高度 1 和 1，取较大值再加一，返回 2。
访问节点 7 · 叶子：节点 7 是叶子，左右子树均为空。两个子调用返回零后，本节点将返回一。
回传 7 · 子树高度 = 1：节点 7 收到左右子树高度 0 和 0，取较大值再加一，返回 1。
回传 9 · 子树高度 = 3：节点 9 收到左右子树高度 2 和 1，取较大值再加一，返回 3。
访问节点 20：进入节点 20 的调用。父调用暂时保留，先递归计算左右子树，当前高度还不能返回。
访问节点 15 · 叶子：节点 15 是叶子，左右子树均为空。两个子调用返回零后，本节点将返回一。
回传 15 · 子树高度 = 1：节点 15 收到左右子树高度 0 和 0，取较大值再加一，返回 1。
访问节点 8 · 叶子：节点 8 是叶子，左右子树均为空。两个子调用返回零后，本节点将返回一。
回传 8 · 子树高度 = 1：节点 8 收到左右子树高度 0 和 0，取较大值再加一，返回 1。
回传 20 · 子树高度 = 2：节点 20 收到左右子树高度 1 和 1，取较大值再加一，返回 2。
回传 3 · 子树高度 = 4：节点 3 收到左右子树高度 3 和 2，取较大值再加一，返回 4。
答案：整棵树的最大深度为 4：递归算得整棵树高度为四。换成显式栈时，改为从根向下记录层数：根为一，孩子比父节点多一。
空树、单节点与只有一个孩子的链，都应得到正确结果；链长就是这棵树的最大深度。
广度优先、递归高度与显式栈层数可以求同一答案，但状态含义和保存的数据不同。
参考代码
class Solution: def maxDepth(self, root): if root is None: return 0 stack = [(root, 1)] best = 0 while stack: node, depth = stack.pop() best = max(best, depth) if node.left is not None: stack.append((node.left, depth + 1)) if node.right is not None: stack.append((node.right, depth + 1)) return best复杂度
- 时间：O(n)，每个节点只入栈、出栈一次
- 空间：O(h)，二叉树深度优先显式栈最多 O(h) 个待处理节点；最坏为 O(n)
易错点
面试追问把动画讲成自己的话
追问能用广度优先遍历吗？
追问显式栈中的 depth 是什么？
追问为什么不能把所有地方都叫节点深度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树的直径
LeetCode 543 · 简单 · 沿着 树 继续往下推进