题目描述
返回二叉树中节点 p、q 的最近公共祖先(深度最大的、同时是二者祖先的节点)。
思路解析
最直觉的做法：先 DFS 求出根到 p 的路径、再求根到 q 的路径，然后把两条路径从头逐个比，最后一个相同的节点就是 LCA。能对，但要存两条路径、走两遍、再对齐比一遍，又费空间又啰嗦。
转折：不必显式存路径。dfs(node) 碰到空或碰到 p/q 就把自己返回上去；否则递归左右，谁找到了目标谁就把目标往上传。某个节点若左子树和右子树各传回一个非空，说明 p、q 分居它的两侧——它就是 LCA。这题适合后序，是因为答案要等「左右两边的消息都回来」才能判定。
出发 · 后序先扎到底找 p,q：从根 3 进入。3 不是 p 也不是 q，不能马上决定，得先递归左右、等它们汇报。先往左孩子 5 走。p=6、q=2 已用蓝色标出。
下探到 5 · 再往两边问：到节点 5：它本身不是目标，同样要先问它的左右孩子 6 和 2。继续往左孩子 6 下探。
命中 p=6 · 返回 6 给父亲 5：到节点 6：它就是 p，命中！立刻把自己返回上去，不再往下。于是 5 的左子树收到一个非空结果 6。
命中 q=2 · 返回 2 给父亲 5：回到 5 再走右孩子 2：它是 q，命中！返回 2。现在 5 手里：左 L=6、右 R=2，两侧都非空。这正是「分叉」的信号。
5 左右各一个 · 5 就是 LCA：节点 5 同时从左、右收到非空结果，说明 p、q 一边一个——5 就是最近公共祖先。此后 5 把「自己」作为结果返回给父亲 3。
5 把 LCA 上传 · 转看右支：5 把「自己(LCA)」返回给父亲 3，成为 3 的左子树结果 L=5。但 3 还没法下结论——必须把右孩子 1 也问完，才知道 3 是不是又一个分叉点。
负例分支 · 1 的子树里没有目标：递归进 3 的右孩子 1 的子树 (0,8)：里面既没有 6 也没有 2，左右都返回 None，于是 dfs(1) = None。这是「这一侧什么都没找到」的负分支。
根 3 · 只有一侧有 → 上传那侧：根 3 收到：左 L=5、右 R=None。不是两侧都有，所以 3 不是分叉点，只把非空那侧的 5 原样上传。最终答案就是 5。可见 LCA 是「两侧汇合」的最低点。
后序遍历就是「子树先把消息报上来，父节点再汇总」。每个节点上报「我子树里找到了谁」，第一个同时从左右收到目标的节点就是 LCA。这套汇报思路也用在「带父指针 LCA」「BST 版 LCA」上。
参考代码（Python）
1def lca(node, p, q):
2 if not node or node is p or node is q:
3 return node # 空 或 命中 p/q，返回自己
4 L = lca(node.left, p, q) # 左子树找到了谁
5 R = lca(node.right, p, q) # 右子树找到了谁
6 if L and R: return node # 左右各一个 → 当前是分叉点
7 return L or R # 只有一侧有，上传那侧复杂度分析
- 时间复杂度：O(n) —— 最坏每个节点访问一次
- 空间复杂度：O(h) —— 递归栈深度等于树高 h
套路模板
记住骨架：命中即返、左右都递归、都非空则当前是分叉点、否则上传非空侧。LCA 及其变体都从它来。
1def dfs(node):
2 if not node or 命中(node): return node
3 L, R = dfs(node.left), dfs(node.right)
4 if L and R: return node # 左右都有 → 当前是答案
5 return L or R # 否则上传非空那侧易错点
- 错误写法：只判一侧：L 非空就直接 return node → 正确写法：必须 L 和 R 都非空才是 LCA（只一侧有目标说明 p、q 还没分叉，当前不是最近祖先，应上传那侧继续往上找）
- 错误写法：找到一个目标就提前停止递归 → 正确写法：左右两边都要递归完再合并判断（要等左右消息都回来，才能确定是不是「两侧汇合」的分叉点）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。