题目描述
求二叉树的最大深度(从根到最远叶子的节点数)。
思路解析
直觉是枚举所有「根→叶」路径数节点取最长。可路径条数随分叉爆炸，而且同一段子树被反复走——3→20 这段在 3→20→15 和 3→20→7 里各走一次。
转折：每个节点的深度只取决于它左右子树各自的深度，取较大的 + 1（算上自己这层）。所以一次后序遍历、每棵子树只算一次就够，不用重复走路径。空树深度 = 0，是递归触底的基准。
出发 · 后序先扎到底：从根 3 进入递归。后序的规矩：先把左右子树的深度都问出来，再算自己。先往左孩子 9 走。
左孩子 9 · 叶子 depth=1：9 没有孩子，左右子树深度都是 0，depth(9) = 1 + max(0,0) = 1。把 1 返回给父亲 3。
右孩子 20 · 先递归它的孩子：回到根，走右孩子 20。它有孩子，不能直接算，得先下探到 15、7。（9 已算完，标灰）
20 的左孩子 15 · depth=1：15 是叶子，depth(15) = 1。返回给父亲 20。
20 的右孩子 7 · depth=1：7 也是叶子，depth(7) = 1。返回给 20。现在 20 的左右深度都拿到了。
节点 20 · 1+max(1,1)=2：20 结算：depth(20) = 1 + max(depth(15)=1, depth(7)=1) = 2。把 2 返回给根 3。
根 3 · 收集左右深：根 3 的两个孩子都回来了：左深 L=1、右深 R=2。这里是关键：要取较大的那条，不能只看左边的 1。
根 3 · 1+max(1,2)=3：depth(3) = 1 + max(1, 2) = 3，对应最长路径 3→20→15（或 7）。若只走左边 9 那条会得 2，漏掉更深的右子树——这正是要 max 的原因。
「先递归拿到左右子树的答案，再合并成当前节点的答案」是树形问题的万能套路(后序/树形DP)：深度、直径、平衡判断、最大路径和全靠它。
参考代码（Python）
1def maxDepth(self, root):
2 if not root: return 0 # 空树深度 0（递归的底）
3 L = self.maxDepth(root.left) # 左子树深度
4 R = self.maxDepth(root.right) # 右子树深度
5 return 1 + max(L, R) # 取大 + 自己这层复杂度分析
- 时间复杂度：O(n) —— 每个节点算一次
- 空间复杂度：O(h) —— 递归栈 = 树高
套路模板
记住骨架：空返回基准、递归拿左右答案、合并成当前答案。换"合并"的公式就解不同题：深度用 1+max、节点数用 1+L+R。
1def dfs(node):
2 if not node: return 基准值 # 空节点的答案
3 L = dfs(node.left) # 左子树的答案
4 R = dfs(node.right) # 右子树的答案
5 return 合并(L, R, node) # 拼成当前节点的答案易错点
- 错误写法：空树返回 1 → 正确写法：空树返回 0（空树没有节点，深度是 0，叶子才是 1）
- 错误写法：只算一条路径 → 正确写法：取左右子树的 max（深度看最长那条路）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。