题目描述
返回二叉树中两个节点 p、q 的最近公共祖先(深度最大的公共祖先)。
树 = 3 →(5,1), 5 →(6,2)
p, q = 6, 2
输出 = 5
思路解析
dfs(node)：碰到空、或者碰到 p / q 就返回该节点。否则递归左右——如果左子树和右子树各返回了一个非空（说明 p、q 分居两侧），那当前节点就是 LCA；如果只有一侧有，就把那侧的结果往上传。
标记目标 p=6, q=2：要找 p=6、q=2（蓝色）。从根 3 开始递归下去找它们。
在 5 的左子树找到 6：递归到节点 5：它的左子树递归返回了 6（找到 p）。
在 5 的右子树找到 2：节点 5 的右子树递归返回了 2（找到 q）。左右各得一个非空！
5 是分叉点 = LCA：节点 5 同时从左、右收到了非空结果，说明 p、q 一边一个——5 就是最近公共祖先。再往上（3）只会从左边收到 5，直接上传。
后序遍历就是"自底向上汇报"：每个节点把"我子树里找到了谁"上报给父亲。第一个同时收到左右两个目标的节点，就是它们的最近公共祖先。
参考代码（Python）
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) —— 递归栈 = 树高
套路模板
记住骨架：命中即返、左右递归、都非空则当前是分叉点、否则上传。LCA 及其变体（带父指针、BST 版）都从它来。
Python
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 # 否则上传非空那侧易错点
- ❌ 找到一个就停 → ✅ 左右都要递归完再判断（要等左右都回来才知道是不是分叉点）
- ❌ 只有一侧有也返回 node → ✅ 一侧有就上传那侧结果（LCA 是"两侧汇合"的最低点）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。