最近公共祖先

最直觉的做法：先走一遍求出根到 p 的路径，再走一遍求出根到 q 的路径，然后把两条路径从头逐个比，最后一个相同的节点就是答案。能对，但要存两条路径、走两遍、再对齐比一遍，又费空间又啰嗦。

转折来了：不必显式存路径。dfs(node) 碰到空、或碰到 p、或碰到 q，就把自己往上返回；否则先递归左右孩子，谁找到目标谁就把目标往上传。某个节点如果左右两边各传回一个非空，说明 p、q 分居它的两侧，它就是 LCA。要等左右消息都回来才能判，所以用后序。

出发 · 标出目标 p=6, q=2：从根 3 进入，它现在是橙色当前节点。3 不是 p 也不是 q，不能马上决定，得先递归左右、等它们汇报。蓝色的 6 和 2 就是要找的 p、q。先往左孩子 5 走。

下探到 5 · 再往两边问：走到节点 5，它变成橙色当前节点。5 本身不是目标，同样得先问左右孩子 6 和 2。先往左孩子 6 下探。

命中 p=6 · 把 6 返回给 5：走到节点 6，它就是 p，命中。6 变绿，立刻把自己返回上去，不再往下递归。于是 5 的左边收到一个非空结果，记作 L 等于 6。

命中 q=2 · 把 2 返回给 5：回到 5，再走右孩子 2，它是 q，命中。2 变绿、返回 2。现在 5 手里两边都有了：左 L 等于 6、右 R 等于 2，两侧都非空。这正是「分叉」的信号。

灵魂帧 · 5 左右都非空 → 5 就是 LCA：把镜头停在节点 5：它左边收到 6、右边收到 2，两个都不是空。这说明 p、q 一边一个，分居 5 的两侧。判定成立——5 就是最近公共祖先。这一帧就是整题的核心：第一个左右都收到非空的节点。

5 把自己当答案 · 上传给父亲 3：5 被判定为 LCA 后，把「自己」当作结果返回给父亲 3，成为 3 的左结果 L 等于 5。但 3 还不能下结论，必须把右孩子 1 也问完，才知道 3 会不会又是一个分叉点。

负分支 · 1 的子树里没有目标：再看 3 的右孩子 1，它现在是橙色当前节点。递归进它的子树 0 和 8，里面既没有 6 也没有 2，左右都返回 None。所以 dfs(1) 也返回 None。这是「这一侧什么都没找到」的负分支。

根 3 · 只有一侧有 → 原样上传那侧：最后回到根 3，它左边收到 5、右边收到 None。不是两侧都有，所以 3 不是分叉点，它只把非空那一侧的 5 原样往上传。最终答案就是 5。可见 LCA 就是「两侧汇合」的最低那个点。

后序遍历就是「子树先把消息报上来，父节点再汇总」。每个节点上报「我子树里找到了谁」，第一个同时从左右收到目标的节点就是 LCA。这套汇报思路也用在带父指针的 LCA、BST 版 LCA 上。

雷区实演 · 只判一侧会错在哪：换个例子想想：如果 q 改成 8、在右支里。走到 5 时，它左边收到 6、右边是 None。正确做法是只把 6 上传，让 3 去汇合 6 和 8。但若错写成「左边非空就 return 5」，就会把 5 当答案，漏掉真正的分叉点 3。所以一定要左右都非空才行。

面试追问：面试追问的重点，是把动画里的状态定义、为什么用后序、边界和复杂度讲成自己的话。

迁移阶梯：把这题练到能复述后，再去同类题迁移：LC235 的 BST 版 LCA 用有序性更省；LC1650 给了父指针可以转成链表相交。点开右侧的「二叉树」专题继续刷，写不出来时让 AI 助教小欧带你拆解。

边界三连：最近公共祖先的边界，先看 p 是 q 祖先、p、q 在根两侧、以及退化成链这三种会触发特殊分支的极端样例。