二叉树最近公共祖先（LCA）递归解法详解：Java面试必备

2026年刷题日志翻到这一页标题写的是“Lc339-二叉树的最近公共祖先”底下标注“树、递归、java”。最近公共祖先Lowest Common Ancestor简称LCA是二叉树面试题里的钉子户Java岗的笔试、面试手写代码环节都爱拿它试水。不过严格说LeetCode上236题才是经典版339题其实是Nested List Weight Sum网上也能看到不少平台或者个人笔记把编号写得不太统一这倒不影响我们今天要讨论的算法本身。很多朋友看到这道题第一反应是“我知道要用递归但就是不知道返回值该怎么设计”今天我就把这套递归思路、Java实现、还有面试追问时容易翻车的地方一次性讲透。1. 先从题目本身说起LCA到底在找什么1.1 题目描述与直觉理解给定一棵二叉树根节点记作 root再给你两个节点 p 和 q要求找出它们的最近公共祖先。什么叫“最近公共祖先”先搞懂两个词公共祖先既是 p 的祖先又是 q 的祖先的节点。最近公共祖先在所有的公共祖先里距离 p 和 q 深度最远的那一个也就是自下而上遇到的第一个公共祖先。注意题目里通常会有一个容易被忽略的约定一个节点可以是它自己的祖先。也就是说如果 p 是 q 的父节点那么 p 自己就是 p 和 q 的最近公共祖先。这一点如果不提前看清楚写代码的时候很容易在 root p || root q 这个判断上犹豫半天。举个例子一棵这样的树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4节点 6 和节点 4 的最近公共祖先是 5。节点 5 和节点 1 的最近公共祖先是 3。节点 5 和节点 4 的最近公共祖先还是 5因为 5 是 4 的某一级祖先同时 5 是自己的祖先。这种题在LeetCode上一半以上的提交是Java写的原因很简单树和递归本来就是Java后端开发面试的高频区二叉树遍历、二叉树深度、搜索二叉树这些基础问题都会用到同一种思维链路而LCA把这个链路推到了稍微复杂一点的分支判断上。1.2 为什么感觉比普通遍历难一个台阶很多朋友能把前序、中序、后序遍历背得滚瓜烂熟一到LCA就卡住。原因在于遍历只是“按顺序访问节点”而LCA要求的不是“访问”是“根据两个节点的位置做出判断”。你必须在递归的过程中同时追踪两个目标节点这就要求递归函数的返回值承担更多含义。如果用一个词概括这题的核心思维那就是“自底向上”。遍历整棵树把左子树和右子树的查找结果都拿到手里之后当前节点再做最终决断——本质上就是后序遍历思想的延伸。很多人一上来想的是从上往下走试图碰运气直接定位到公共祖先这种思路很容易走入死胡同。真正的解法是先让递归深入到最底层再一层一层把答案“带出来”。1.3 这题在面试和比赛中的真实地位LCA是那种“看起来不大却能把一批人筛出去”的题目。2026年的Java招聘里手撕算法仍然在面试过程中占着不低的比例除了八股文、MyBatis、Spring Boot这类框架问题之外二叉树相关题目几乎是必练盘。蓝桥杯、校招笔试里二叉树的最近公共祖先也经常以原题或者变形题出现。面试官考这道题的目的还不是让你背答案而是考察三件事递归出口设计是否严谨、对自底向上思想是否理解到位、能不能在追问之下把复杂度分析和异常情况讲清楚。只默写出代码但说不清为什么大概率会被追加追问打回原形。2. 递归解法的核心思路自底向上把答案“汇聚”出来2.1 先想明白递归函数的返回值到底在表达什么LCA问题的递归代码只有十几行但每一行return都值得琢磨。我见过太多人背完代码就忘本质原因是没搞懂这个递归函数返回来的东西到底代表什么。这个递归函数返回的并不是“以当前节点为根的子树中的最近公共祖先”。它返回的是在“以当前节点为根的子树”里对最终答案有贡献的那个节点。什么叫做有贡献分三种情况如果子树里找到了 p就返回 p。如果子树里找到了 q就返回 q。如果某个节点发现自己的左子树和右子树各找到了一个目标节点那这个节点就是答案返回它自己。第三种情况的返回是这一个节点向上传递的过程中不再会被替换。换句话说答案一旦在底层产生就会一路原封不动地被传回根节点。这个语义设清楚之后代码就不再是死记硬背了。2.2 把树想象成公司组织架构用一个生活化的类比帮自己建立直觉。把整棵树当成一家公司的组织架构根是CEO中间是各级主管叶子是基层员工。现在要找一个组里两个成员p和q的最近共同上级。每个节点先问自己的左下属部门和右下属部门你们这边有没有我们要找的两个人汇报结果可能有这么几种左边找到了一个人右边又找到了另一个人——好了不用往上汇报了当前这个节点就是他俩的最近共同上级。只有一边找到了人另一边没找到——说明这两个人都在同一条汇报线上或者其中一个还没找全把找到的结果继续往上传。两边都没找到——上报一个“没找到”。这个类比最妙的地方在于它天然就是自底向上的先让下面的部门自查结果层层汇总而不是从上往下乱点鸳鸯谱。递归代码的执行过程也正是这么一回事。2.3 为什么后序遍历是这个解法的灵魂先看代码再拆逻辑public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) { return root; } TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) { return root; } return left ! null ? left : right; }只有六行核心逻辑但每一步都有讲究。两步检查可以这么理解你开始自查根节点为空当然什么都返回不了根节点本身就是p或q那就把它交出去。然后才是分别去左子树和右子树里递归查找。最终的分支判断是灵魂所在如果 left 和 right 都不为空说明 p 和 q 一个在左子树、一个在右子树当前节点就是它们的最近公共祖先。如果只有一个不为空说明两个目标节点都在同一边把不为空的那一侧结果向上返回。如果两个都为空走到最后一行时会返回 null表示这棵子树里什么都没找到。注意这里并不是“一眼看穿了答案”而是先把左右子树的结果都拿到手再反过来判断当前节点的角色。这正是后序遍历的天然优势你永远可以先知道孩子的信息再决定自己怎么处理。而“最近公共祖先”这个答案恰恰需要建立在“左右两侧各自的情况都已知”的前提之上。2.4 一个具体例子的完整递归过程还是用前面那棵树求节点 6 和节点 4 的最近公共祖先从根节点 3 开始先递归左子树根节点 5。在节点 5 处左递归到 6发现 6 就是 p返回 6右递归到 2继续深入在 2 的左子树找到 7右子树找到 4此时节点 2 发现自己左右都不为空返回 2。节点 5 拿到 left 6right 2两边都有值于是返回 5。根节点 3 的左子调用拿到 5右子树递归到 11 的子树里既没有 6 也没有 4返回 null。根节点 3 看到 left 5right null于是返回 5。答案就是 5。整个过程里递归沿着树先沉到底再按后序的顺序一层层往回弹每个节点的判断都发生在“子节点已经报告完毕”之后所以绝不会出现错把深层的某条路径当成公共祖先的情况。3. Java 版本实现完整代码与逐行注释3.1 完整可运行代码实际刷题时我们通常直接在一个类里写方法TreeNode 结构题目已经给出。为了完整起见我把树的定义也写出来方便自己用 IDE 调试class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } } class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) { return root; } TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) { return root; } return left ! null ? left : right; } }这段代码在LeetCode上是标准解几乎所有题解区都有类似写法。你可以直接提交。3.2 逐行拆解每一步return的理由关键就两行判断。第一处递归进入时的快速返回if (root null || root p || root q) return root;。这里把三种情况合并处理了空节点没有讨论价值返回null当前节点是p说明p在这棵子树的顶部p本身的祖先链在更上层所以直接把p交出去即可当前节点是q也一样。很多初学者会问如果p在左子树但是q也在这个子树里这里返回p会不会丢了q不会。因为这里的“返回p”只是给上层用的一个结果上层节点会继续拿着这个结果和另一侧的结果做比较只有在某个子树内同时遇到p和q才会触发“左右都不为空”的分支不会误判。第二处递归回溯时的判断if (left ! null right ! null) return root;。这句话是整个算法的收网时刻。左右子树各自返回了一个非空节点那说明p和q就分布在当前节点的两侧当前节点自然是最近公共祖先。这里值得再深入一层为什么不会是更底层的某个节点因为更底层的节点如果已经是公共祖先它的返回值就不会是一个单一节点而是它自己并且这个值会在本次递归的上一层被传上来——当传到一个节点时如果它看到左右都不为空说明当前节点是p和q路径第一次“分叉”的地方也就是深度最大的公共祖先。最后一行return left ! null ? left : right;是一个巧妙的合并写法如果left非空说明p和q都在左子树这一条路上返回left否则说明结果在右子树返回right如果两个都为空返回的是null表示没找到。它把“只要一边有结果就带上去”这个动作压缩进了一行。3.3 复杂度分析与边界情况处理时间复杂度 O(n)因为每一个节点至多被访问一次空间复杂度 O(h)h 是树的高度也就是递归调用栈的最大深度。最坏情况是树退化成一条链比如每个节点只有右孩子这时递归深度会达到 n空间复杂度退化为 O(n)在极端大的数据下可能触发栈溢出。这也是面试官非常喜欢追问的点递归写法能不能改成迭代写法答案是可以用HashMap记录父节点或者用显式栈模拟后序遍历都能做到后面我会在扩展部分给代码。边界情况方面建议在写代码前把下面几类在脑子里过一遍root 为空时返回 null逻辑上直接由第一个分支覆盖。p 就是 rootq 在 root 的某棵子树中返回 root。第一分支的 root p 直接命中。p 和 q 是同一个节点返回该节点即可。p 和 q 都不在树中题目保证不会出现这种情况但如果出现上述代码会返回 null 或者返回其中一个误当答案。LeetCode上题目明确保证两个节点一定存在于树中所以可以不处理但面试时一定要主动说清楚这个前提能看出你对题目条件的敏感度。4. 我踩过的坑和面试里常见的追问4.1 面试场景中最容易翻车的几个细节我第一次写这道题的时候犯过一个很傻的错误把root p || root q的判空和对 target 的判断分开了结果某个分支出现了空指针。后来想明白了合在一起写不是炫技是为了兼顾可读性的同时减少空指针风险。还有一种很常见的错误是把递归返回结果和“是否找到”混为一谈。有人会在 left 和 right 都不为 null 时返回 root这个没错但有人会把“left ! null || right ! null”当成继续递归的条件写进 while 或者 if 里导致永远递归不出结果。这其实还是语义没想清楚left 和 right 不为空意味着子树里已经找到了答案或者找到了一半答案你现在的职责是上传而不是继续追踪。运行时错误在刷题平台上也经常出现。Java 选手最容易遇到的报错是 StackOverflowError一般出现在树特别深的情况下比如链表型的树这种时候递归的深度等于节点数量栈很容易爆掉。程序里出现这个错误后系统的第一反应不是“递归逻辑错了”而是“递归深度没控制住”。应对方案有两个一是遍历方式不变改成显式栈迭代二是确认题目给出的树是否符合平衡假设。强烈建议你把这个前提在面试开始时就说出来“如果树退化成链表递归写法可能栈溢出需要迭代方案兜底。”4.2 面试官高频追问如果p和q不保证存在怎么办这是我在实际面试中被问过的问题比单纯背题高级得多。题目本来保证p和q都在树中但面试官想看你是否会主动考虑“不保证存在”的场景。如果p不在树中上面的解法可能会错误地返回q因为只找到了一个目标就会把另一个目标节点作为答案往上传。正确的处理办法是改变递归函数的返回值语义让它返回一个带计数信息的结果。我一般用一个简单的小结构class Result { TreeNode node; int count; // 找到了几个目标节点 Result(TreeNode node, int count) { this.node node; this.count count; } }递归时统计当前子树里一共找到了 p 和 q 中的几个如果 count 2说明这个子树同时包含两个目标节点此时如果左右子树返回的 node 不同当前节点就是答案如果只找到一个就返回找到的那个节点同时 count 为1如果什么都没找到返回 nullcount 为0。最后检查根节点的返回值如果 count 2直接返回 null表示树中根本不存在完整的两个目标节点。这个变体出现的频率不低尤其在面试官想把你从“背题型选手”和“理解型选手”里区分开的时候。4.3 追问中的复杂度证明和迭代写法追问“为什么空间复杂度是 O(h)”也很常见。你需要说清楚递归调用栈的深度等于从根到叶子最长路径的长度也就是树高。对于一棵平衡二叉树h 约等于 log n对于链式树h 就是 n。所以空间复杂度写成 O(h) 比直接写 O(n) 更准确也更能体现你的功底。如果追问迭代写法可以给出用 HashMap 记录父节点的方案public TreeNode lowestCommonAncestorIterative(TreeNode root, TreeNode p, TreeNode q) { MapTreeNode, TreeNode parent new HashMap(); DequeTreeNode stack new ArrayDeque(); parent.put(root, null); stack.push(root); while (!parent.containsKey(p) || !parent.containsKey(q)) { TreeNode node stack.pop(); if (node.left ! null) { parent.put(node.left, node); stack.push(node.left); } if (node.right ! null) { parent.put(node.right, node); stack.push(node.right); } } SetTreeNode ancestors new HashSet(); while (p ! null) { ancestors.add(p); p parent.get(p); } while (!ancestors.contains(q)) { q parent.get(q); } return q; }思路很直白先遍历整棵树把每个节点的父节点记下来然后从 p 出发沿着父节点链往上走把所有祖先都放到集合里再让 q 也沿着父节点链往上走第一个在集合里出现的 q 的祖先就是答案。这种方式的优点是避免了递归栈溢出缺点是需要额外的 HashMap 和 HashSet 空间面试的时候可以和递归方案对比着讲显得你掌握的工具不止一把。4.4 变体题二叉搜索树版本如果题目把普通二叉树换成二叉搜索树BST整个问题会简单一大截。BST 的特点是左子树所有节点值小于根节点右子树所有节点值大于根节点。利用这个性质我们压根不用递归遍历全树从上往下走就行public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) { while (root ! null) { if (p.val root.val q.val root.val) { root root.left; } else if (p.val root.val q.val root.val) { root root.right; } else { return root; } } return null; }当 p 和 q 的值都小于当前节点时说明它们都在左子树那答案也在左子树都大于当前节点时答案在右子树一个在左一个在右当前节点就是答案。时间复杂度降到了 O(h)很多时候是面试官顺带的追加题。5. 从这道题看递归的通用套路5.1 一个能套用到很多树题里的递归模板把 LCA 的代码简化成思维模板其实就三步确定递归出口。先处理 null再处理“当前节点是不是目标之一”。分头递归左右子树收集结果。根据左右结果的关系做判断两边有货当前是答案单边有货向上传两边没货返回空。这个模板几乎可以处理一大类二叉树问题。比如求两个节点的距离先算出 LCA再用深度差求得每个节点到 LCA 的距离相加即可比如判断一棵树是不是另一棵树的子树也可以用类似的“子树上是否完全匹配”的递归思路再比如求二叉树的最大深度其实也是把左右子树的结果拿回来比大小再返回。你一旦抓住“先收结果、再做决策”这个套路很多树的题都不再是孤立的知识点。多叉树版本的 LCA 也是同一个模板。把 left/right 换成遍历所有孩子统计返回结果里非空的数量如果非空数量等于 2当前节点就是答案等于 1向上传这个唯一结果等于 0返回空。真正理解了递归语义之后这个扩展只需要十分钟就能写出来。5.2 关于递归学习的一点个人体会我不建议你直接背 LCA 的答案因为面试官只要多追问一句“为什么这里返回 left 而不是 root”你就会露馅。更好的学习方式是在白板上给自己写一段语义注释先把“递归函数返回什么”写清楚再动手填代码。我2026年在准备面试时重新整理这道题发现自己第一次能把所有分支都解释顺就是因为在代码开头补了一句注释返回值为在 current 子树中对答案有贡献的节点。这句话看似简单但它把过去死记硬背的模糊理解彻底钉死了。如果在调试过程中你发现自己写的版本总是在某个测试用例上报错先不要急着翻题解。打开 IDE用一个只有三五个节点的小树手动画出递归调用树把每一次返回的节点标出来对照一下哪一层开始偏离预期。这个排查过程大概只需要十分钟但对思维的锻炼价值比直接看答案高得多。二叉树的题本质上就是在训练这种“把抽象逻辑落实到每一步返回值”的能力LCA则是这个训练里最好的入口之一。