【码道初阶】【LeetCode 236】二叉树最近公共祖先：我是如何用几行递归搞定这个面试高频题的？

【LeetCode 236】二叉树最近公共祖先：我是如何用几行递归搞定这个面试高频题的？

在二叉树的面试题中，“最近公共祖先”（Lowest Common Ancestor，简称 LCA）绝对是出现频率最高的题目之一。

初看题目，可能觉得有点绕：既要是祖先，深度还要尽可能大。但其实，只要我们转换一下视角，用后序遍历（自底向上）的思维去理解，这道题的代码逻辑简直优雅得让人惊叹。

今天，我就结合我写的这段 Java 代码，带大家像剥洋葱一样拆解这道题的递归思路。

1. 核心思维：把“寻找”变成“汇报”

解决这道题，我的核心策略是**“自底向上汇报”**。

你可以把每一个节点想象成一个部门经理。题目要求我们在整棵树里找p和q。
作为根节点（大老板），我不知道p和q在哪，但我可以派我的左右手（左子树和右子树）去搜。

• 我对左孩子说：“你去你的辖区找找，有没有p或者q？只要看到其中一个，就赶紧告诉我。”
• 我对右孩子说：“你也去你的辖区找找，同上。”
• 等他们回来汇报结果后，我再根据情况做判断。

这就是后序遍历的精髓：先搜左右，最后再处理根节点的逻辑。

2. 代码深度拆解

让我们看着代码，一行一行来翻译我的“内心戏”。

classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null)returnroot;if(root==p||root==q)returnroot;TreeNodeleftTree=lowestCommonAncestor(root.left,p,q);TreeNodeRightTree=lowestCommonAncestor(root.right,p,q);if(leftTree!=null&&RightTree!=null){returnroot;}elseif(leftTree!=null){returnleftTree;}else{returnRightTree;}}}

第一步：终止条件（遇到死胡同或找到目标）

if(root==null)returnroot;// 或者 return nullif(root==p||root==q)returnroot;

这是递归的**“触底反弹”**时刻。当我走到当前节点root时，我有两个理由停止向下搜索：

1. 到了空节点（root == null）：这里啥也没有，死胡同，返回null（代码中写return root也是返回 null）。
2. 找到了目标（root == p 或 root == q）：这里有一个关键点！如果我发现当前节点就是p或者q，我不需要再往下找了。直接把我自己（root）返回上去。
   • 潜台词：“报告长官，我在这个位置发现了嫌疑人 P（或者 Q）！”

第二步：下发任务（递归搜索）

TreeNodeleftTree=lowestCommonAncestor(root.left,p,q);TreeNodeRightTree=lowestCommonAncestor(root.right,p,q);

这两行代码就是“派人出去搜”。

• leftTree存的是左那边搜寻的结果。
• RightTree存的是右那边搜寻的结果。

注意，递归函数会一直钻到底，直到触发第一步的终止条件，才会带着结果一层层返回。

第三步：汇总决策（我是不是祖先？）

这是整段代码的灵魂，也是很多人容易晕的地方。我现在拿到了左右手下的汇报结果leftTree和RightTree，现在我要通过这三个if-else来判断情况：

情况 A：左右都有发现 -> 我就是 LCA

if(leftTree!=null&&RightTree!=null){returnroot;}

如果leftTree不为空（说明左边找到了一个），而且RightTree也不为空（说明右边也找到了一个）。
这意味着什么？意味着p和q分别在我的左边和右边。
既然一个在左一个在右，那我不就是他们相遇的那个分岔路口吗？
所以我就是那个最近公共祖先！直接返回我自己（root）。

情况 B：只有左边有发现 -> 结果在左边

elseif(leftTree!=null){returnleftTree;}

如果左边回报说“找到了”，而右边回报说“全是 null”。
说明p和q都在我的左子树里（或者其中一个在左边，另一个根本不在树里，但题目保证一定在）。
既然都在左边，那我这个“当前节点”就不是最近的祖先，真正的结果是左手汇报上来的那个节点。于是我做个顺水人情，把leftTree继续往上传递。

情况 C：只有右边有发现（或都为 null） -> 结果在右边

else{returnRightTree;}

同理，如果左边是空的，那结果一定在右边。直接把RightTree返回上去。

3. 一个特殊的疑问：如果一个节点是另一个的祖先怎么办？

有同学可能会问：“如果p是5，q是1，而结构是5 -> ... -> 1，你的代码会先遇到5就直接返回了，不会去搜下面的1吗？”

你是对的，但这正是代码巧妙的地方！

回顾一下终止条件：if(root == p || root == q) return root;

如果我先遇到了p（比如节点 5），我直接返回5。我根本不会去遍历5的子树，所以我也不会去刻意找q。
但在这种情况下，p本身就是p和q的最近公共祖先。
所以，直接返回p是完全正确的逻辑！代码自动涵盖了“一个节点是另一个节点祖先”的特殊情况。

4. 总结

这段代码虽然短，但逻辑非常严密：

1. 遇到 null-> 返回 null。
2. 遇到 p 或 q-> 返回当前节点（找到了）。
3. 左搜右搜-> 拿到左右结果。
4. 左有且右有-> 当前节点就是答案（LCA）。
5. 一边有一边无-> 答案在有结果的那一边。

这就是利用二叉树后序遍历解决 LCA 问题的全部奥秘。与其死记硬背，不如想象成一个“下属汇报、上级决策”的过程，是不是瞬间清晰了很多？

希望这篇博客能帮你彻底拿下这道 LeetCode 高频题！