做二叉树递归题很多人卡住的从来不是 Java 语法而是脑子里没有一棵树。Lc339 这道“二叉树的最近公共祖先”我觉得是最适合用来打通“树 递归”关节的题目解法只有十几行代码信息量却非常大。题目本身不绕给定一棵二叉树和两个节点 p、q找出它们距离最近的公共祖先节点。但真要把需求翻译成递归函数的返回值设计很多新手当场就懵了写完一跑要么空指针要么结果对不上。这篇文章我打算从读题、拆递归、写 Java 实现、构造测试、排查运行时错误一直写到面试变体尽量把每一步为什么这么做都讲透。如果你最近在准备 Java 面试或者刚学完二叉树遍历想找一道经典题练手这篇可以照着敲一遍。1. 把题面先拆干净Lc339 到底在考什么1.1 公共祖先的定义先说清楚公共祖先的定义是对于二叉树中的两个节点 p 和 q如果存在一个节点 x让 p 和 q 都出现在 x 的左子树或右子树中或者 p、q 本身就是一个节点比如 p 就是 x那么 x 就是 p 和 q 的公共祖先。注意“出现在子树中”这个说法它包含了节点本身。举个例子下面这棵树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4p5q1 时公共祖先是 3p5q4 时公共祖先是 5而不是 3p6q8 时公共祖先是 3。这里有个很多人第一次接触会忽略的细节一个节点可以成为自己的祖先。题目里说“最近公共祖先”其实就是所有公共祖先里离这两个节点最近的那一个也就是深度最大、最“低”的那个。p5q4 的情况下节点 5 既是 p 本身又包含了 q所以它比根节点 3 更近答案就是 5。1.2 三个容易忽略的题眼第一LeetCode 题面默认 p 和 q 都在这棵二叉树中而且 p 不等于 q。这是后面递归能写得那么简洁的前提。如果题目改成“节点可能不存在”代码就要复杂不少后面我会单独讲。第二二叉树的节点值在这个问题里并不一定全局唯一但题目会保证 p 和 q 是树中的真实节点引用。所以你在 Java 里可以用来比较节点对象而不是比较val。这一点很关键如果用node.val p.val去判断一旦树里出现重复值结果就很不可控。第三“最近”这个词决定了我们不能从根节点随便找一个公共祖先就结束要找的是最深的那个。所以递归顺序上很有讲究不能一上来就判断根节点必须先获取左右子树的信息再回到当前节点做判断。1.3 为什么这道题天然适合递归而不是迭代二叉树本身就是递归定义的一个节点由值和左右两个子树组成而左右子树仍然是二叉树。Java 里你写一个TreeNode它里面有left和right两个字段指向同类型的节点这种结构天生就适合用递归去处理。迭代当然也能做但思路会绕很多。比如你要记录每个节点的父节点然后从 p 向上走标记一串祖先再让 q 也向上走找到第一个被标记过的节点。这种解法要额外维护一个 Map 或者数组代码规模明显膨胀。而递归解法靠着函数调用栈天然就保留了一条从根到当前节点的路径我们要做的只是让每一层递归合理地向上“汇报”结果。还有一个隐藏考点这道题的结果依赖后序遍历。只有先把左子树和右子树都处理完才能判断当前节点是不是最近公共祖先。如果你按前序遍历“当前节点先判断再进子树”很容易提前返回拿到错误答案。这也是很多人写二叉树递归时最常犯的方向性错误。2. 递归思路自底向上汇报信息2.1 先想清楚递归函数返回什么写递归最忌讳的就是没想清楚返回值就开写。很多初学者把递归函数当成一个“黑盒”然后不断往里面塞参数最后代码越写越乱。Lc339 这个解法递归函数返回值的含义你可以这样定义如果当前子树里既没有 p也没有 q返回 null如果当前子树里找到了 p 或 q 中的某一个返回找到的那个节点如果当前子树里已经确定了最近公共祖先也返回这个祖先节点。最后这一点比较容易忽略。也就是说返回的非空节点有两种身份可能是“在我们还没确定答案的路径上它是 p 或 q”也可能是“在已经找到答案的分支上它就是答案本身”。一个返回值兼有两种含义这正是递归设计的精妙之处。这样设计的好处是我们不需要额外的标志位只要一个引用就能把信息从最底层一路带到最顶层。2.2 后序遍历的三段式写法递归函数的整体框架非常固定我建议直接背下来然后深入理解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;注意顺序一定是先递归左子树再递归右子树最后回到当前节点判断。这种先下后上的顺序就是后序遍历的核心。Java 代码里虽然只是三行但执行过程是完整的“左 - 右 - 根”路径。整个函数唯一的出口条件是if (root null || root p || root q) { return root; }root 为 null 说明这棵子树为空没找到任何目标节点root 是 p 或 q 说明当前节点就是一个目标节点我们直接把 root 返回上去。2.3 用一个小树完整走一遍还是用上面的树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4假设 p5q4。从根节点 3 开始递归进入左子树节点 5发现root p于是直接返回 5。这时候 5 的子树内部包括节点 4根本没有被遍历到。你可能会问那 q4 不就漏了吗实际上不会。因为 p 本身就是 q 的祖先如果 q 在 p 的子树里那 p 就是最深的那一层这个问题已经解决了不需要再往下找。接着右子树节点 1 往下递归从左到右遍历完所有节点发现既不是 p 也不是 q返回 null。所以回到根节点 3 时左子树返回值是 5右子树返回值是 null。此时判断left ! null right ! null不成立于是进入最后一行return left ! null ? left : right;返回 5。答案正确。再看另一个组合p6q8。根节点的左子树返回 6右子树返回 8。两边都不为 null说明 p 和 q 分别分布在当前节点的左右两侧当前节点 3 就是最近公共祖先直接返回 3。2.4 为什么提前返回不会错过“更近的祖先”这是面试里经常追问的点。回到第一种情况p5q4我们在节点 5 提前返回没有看它的子树为什么还知道答案是 5因为当 p 和 q 都在同一个子树里时最近公共祖先一定出现在那个子树里不会跑到当前节点“更上面”去。递归到节点 5 时p 已经找到了而 q 只可能在节点 5 的子树里。如果 q 真的在节点 5 的子树里那节点 5 就是它们共同的祖先并且比根节点 3 更低、更近。如果 q 不在节点 5 的子树里那么节点 5 并不会作为最近公共祖先它会继续向上返回直到某个更上层的节点发现左右子树分别各找到了一个目标节点。所以提前返回是安全的。这种“先局部、再整体”的思路本质上就是把问题拆给左右子树然后靠返回值的“引用”把信息一层层带上来。写熟了之后你会发现它能解决一大类树的递归问题。3. Java 代码实现从骨架到能跑起来3.1 TreeNode 定义和完整可运行代码先复习一下力扣风格的树节点定义public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }Lc339 的核心解法可以直接写在 Solution 类里class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 当前节点为空或者当前节点就是 p/q直接返回 if (root null || root p || root q) { return root; } // 去左子树找 p/q TreeNode left lowestCommonAncestor(root.left, p, q); // 去右子树找 p/q TreeNode right lowestCommonAncestor(root.right, p, q); // 左右子树各找到了一个说明当前节点就是公共祖先 if (left ! null right ! null) { return root; } // 哪边不为空就把哪边的结果向上传递 return left ! null ? left : right; } }代码就这么多可能不到二十行。很多题解里还会把最后一行写成return left null ? right : left;逻辑完全一样。我的建议是只用一种写法并且能说清楚它是在“向上传递非空的那一侧结果”。3.2 关键分支逐行拆解第一句是函数入口判断。root null是递归的自然出口一路递归到叶子节点的空孩子时触发。root p || root q是两个“提前命中”条件它保证了如果 p 出现在某个节点的左子树里那这个节点就会直接作为 left 的结果返回给上一层。第二段是左右子树递归调用。这里有一个很容易被忽视的细节无论左子树返回了什么右子树照常要递归。因为左子树找到 p 不代表右子树就没有 q最坏情况下你需要把整棵树都走一遍。我之前见过有新手在这里写TreeNode left lowestCommonAncestor(root.left, p, q); if (left ! null) return left;结果 p 和 q 分别在左右两侧时答案就错了。你直接返回 left根本不知道右子树还有 q。第三段判断左右返回值都不为空返回 root。这一步对应“p 和 q 当前分布在这个节点两侧”的情况也对应“左子树和右子树都已经各自找到了一个目标节点”的情况。最后一行是信息继续向上传递。如果 left 不为空说明左子树里找到了目标或者已经确定了答案right 为空说明右子树什么都没找到。这时候整个子树里唯一有意义的返回值就是 left所以把它交给上一层。这个传递过程会一直持续到最上层调用。3.3 Java 编码时的几个实用细节第一个细节判断节点是否相等用而不是equals()。在 LeetCode 这种在线判题环境里p 和 q 就是树里的同一个对象引用用对象地址比较又快又准确。如果你在本地自己构造测试树也要保证传入的 p、q 节点真的是树上挂着的节点而不是 new 一个值相同的节点。第二个细节提前处理 p 或 q 为 null 的情况。虽然题目默认不会传 null但工程上做防御性编程是习惯。如果 p、q 任意一个为 null递归里root p永远不会成立最后可能会返回一个不相关的节点或者抛出异常。最简单的做法是在接口入口加一层判断if (p null || q null) { return null; }第三个细节注意你的树节点构建。很多本地调试的运行时错误并不是算法写错了而是构造树的时候没有正确把左右子树连起来。比如你写了node.left a; node.right b;但 a 和 b 是自己 new 出来的并没有真的挂到 root 上那递归访问到一半就会遇到空指针。第四个细节不要试图在一个节点值重复的树上用val判断 p 和 q。前面说过力扣默认保证节点是唯一引用但你自己扩展成“传入两个 int 类型的 val”去找公共祖先时就必须改成遍历比较node.val pVal || node.val qVal并且要想好重复值会造成什么样的歧义。4. 复杂度、递归栈和“运行时错误”的真相4.1 时间复杂度和空间复杂度分析Lc339 的时间复杂度是 O(n)n 是二叉树的节点总数。原因很简单最坏情况下比如 p 和 q 都位于右子树的最深处递归会对大部分节点都访问一遍。每个节点最多被访问一次所以总时间是 O(n)。空间复杂度主要看递归栈的深度而不是整棵树的节点数。平衡二叉树下递归深度是 O(log n)最坏退化成一条链时深度是 O(n)。所以这道题的额外空间开销可以记为 O(height)height 是树高。你可以在面试里把这个结论说清楚面试官一般会顺着追问一句“如果这棵树特别深怎么办”这就引出了下面要说的栈溢出问题。4.2 为什么“写二叉树程序总是报运行时错误”这个词在初学者群里出镜率很高原因通常只有两类一类是 StackOverflowError另一类是 NullPointerException。StackOverflowError 十有八九是递归出口没写好。比如你忘记了root null这个条件递归就会在叶子节点的空子节点上继续无限往下调Java 的调用栈深度有限直接爆栈。还有一种情况是递归出口写了但树的深度太大。Java 默认线程栈大小通常在 512KB 到 1MB具体看 JVM 版本和操作系统。每个栈帧里保存了局部变量、返回值等信息深度到几万层左右就可能溢出。比如一棵深度为十万的退化二叉树用递归做 LCA跑不起来是正常的。算法没错限制在 Java 虚拟机层面。应对策略有两个第一种是调大 JVM 栈空间比如加-Xss10m这种办法在很多本地环境下有效但治标不治本第二种是改成迭代实现把递归栈换成自己手动维护的显式栈或哈希表。工程上真正遇到深度超大的场景我建议直接走迭代方案。NullPointerException 则通常出现在访问某个节点的 left 或 right 时这个节点本身是 null。比如你在递归里写了root.left.val这种代码但 root.left 为 null一运行就报错。这类问题和算法逻辑无关更多是树构造不完整导致的。4.3 非递归迭代解法作为备选这里给一个工程上更稳的非递归写法思路是先用一次遍历记录每个节点的父节点然后再从目标节点向上追溯。Java 里可以用 HashMap 存父节点引用public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { MapTreeNode, TreeNode parent new HashMap(); DequeTreeNode stack new ArrayDeque(); stack.push(root); parent.put(root, null); // 用迭代遍历把整棵树的父节点关系记录下来 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); } } // 从 p 向上走把所有祖先加入集合 SetTreeNode ancestors new HashSet(); while (p ! null) { ancestors.add(p); p parent.get(p); } // 从 q 向上走遇到的第一个在集合里的节点就是 LCA while (!ancestors.contains(q)) { q parent.get(q); } return q; }这个写法的时间复杂度还是 O(n)空间复杂度是 O(n)优点是不受递归栈深度限制。缺点是代码明显更啰嗦而且用 HashMap 存引用在极端情况下内存占用会偏高。面试里我不建议大家上来就甩这种写法可以先讲递归再补充一句“如果树特别深我也可以改成迭代式”。5. 测试用例与排错实录5.1 自己构造一棵测试树写算法题最怕的是只在脑子里空想。我的习惯是在本地 main 方法里把树搭出来然后调用接口打印结果。以第一节那棵树为例public class Lc339Test { public static void main(String[] args) { // 构造节点 TreeNode root new TreeNode(3); TreeNode node5 new TreeNode(5); TreeNode node1 new TreeNode(1); TreeNode node6 new TreeNode(6); TreeNode node2 new TreeNode(2); TreeNode node0 new TreeNode(0); TreeNode node8 new TreeNode(8); TreeNode node7 new TreeNode(7); TreeNode node4 new TreeNode(4); // 连接左右子树 root.left node5; root.right node1; node5.left node6; node5.right node2; node1.left node0; node1.right node8; node2.left node7; node2.right node4; Solution solution new Solution(); TreeNode ans solution.lowestCommonAncestor(root, node6, node8); System.out.println(ans null ? null : ans.val); // 期望输出 3 } }这里的核心点是传入的 p 和 q 必须是用 root.left、root.right 等引用串起来的节点。如果你图省事再new TreeNode(6)一个出来虽然 val 相同但对象引用不同用判断永远也匹配不上。5.2 我平时跑 LCA 用的测试用例清单下面这组用例基本能把边界情况覆盖住建议按顺序跑pq期望输出测试意图节点5节点13左右各一个目标公共祖先是根节点5节点45一个目标是另一个祖先的子树验证提前返回节点6节点83两个目标在不同分支根节点3节点63p 本身就是公共祖先节点7节点42目标在更深的子树内null树的root无null空树边界情况拿到代码第一时间跑第一行和第三行可以先确认大体逻辑对。第二行是最容易出错的如果结果输出了 3说明你的递归逻辑写反了或者提前返回写错了。我之前给别人 review 代码时发现有人把root p || root q这个条件写在递归调用之后判断导致答案永远是根节点原因就是没有理解“自身就是祖先”这个定义。5.3 一个典型的 StackOverflowError 调试过程假设你在一个特别深的测试用例上报了 StackOverflowError。不要慌先看异常堆栈最顶部它会明确指向递归函数里某个具体行。然后用排除法第一步检查递归出口。如果你的函数里没有写if (root null) return null;那在叶子节点的空孩子上就会无限递归。这种情况最常见代码里补上这个出口就行。第二步判断是不是树本身退化成了单链表。比如所有节点都只有右孩子那递归深度就是节点总数。你可以在本地用一个小规模退化树跑一下比如 5000 个节点如果还报 StackOverflowError说明问题确实出在深度上。第三步尝试调大栈空间或者换成迭代解法。调大 JVM 栈可以快速验证思路但不能作为最终答案提交。我建议把上一节那个迭代写法的测试用例跑一遍确认结果一致以后面对这种输入就有底了。我还在调试时习惯在递归函数里加一行临时输出System.out.println(visit: (root null ? null : root.val));跑完一遍你就能看到递归实际访问的节点顺序。排查结束后记得删掉这些输出不然放在大树上会打出海量日志本末倒置。6. 面试追问与变体扩展6.1 从这道题引申出来的二叉树高频题Lc339 不是孤立的一道题。它的方方面面都能和“二叉树的遍历”“二叉树的深度”“搜索二叉树”“线索二叉树”这些关键词搭上关系。先说二叉树的遍历。Lc339 表面上是找公共祖先实际应用的是后序遍历只是返回值从 void 变成了 TreeNode。如果你把先序、中序、后序遍历的递归结构练得很熟这道题你只看一眼代码结构就能反应过来。再说二叉树的深度。求二叉树最大深度的递归代码也是自底向上max(maxDepth(root.left), maxDepth(root.right)) 1。这和 Lc339 的“先递归子树再处理当前节点”有着完全一样的骨架。把这两道题放一起做相互验证理解会深很多。至于线索二叉树虽然它的核心是把空指针利用起来实现中序线索遍历但它的节点定义和递归遍历思路和普通二叉树是相通的。理解普通二叉树的左右子树递归关系后看线索二叉树会轻松很多。6.2 如果是搜索二叉树代码可以更快如果题目给的不是普通二叉树而是二叉搜索树BST那我们可以充分利用左子树所有节点值都小于根、右子树所有节点值都大于根的特点把递归优化成单路径查找。Java 可以这样写public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) { while (root ! null) { if (p.val root.val q.val root.val) { // p 和 q 都在左子树 root root.left; } else if (p.val root.val q.val root.val) { // p 和 q 都在右子树 root root.right; } else { // 当前节点在 p 和 q 的中间或者当前节点就是 p/q return root; } } return null; }这段代码的时间复杂度最坏是 O(n)平均表现是 O(log n)空间复杂度 O(1)。和通用递归解法的最大区别是它不需要遍历整棵树只沿着一条分支往下走。面试时如果你能先给出通用解法再补充“如果题目改成了搜索二叉树我还能优化成迭代”这会是明显的加分项。6.3 更复杂的变体p 或 q 可能不存在很多厂商面试不会只满足于默写代码。最常见的追问是把条件改成“p 和 q 不一定存在于树中找到它们的最近公共祖先如果不存在就返回 null”。这个条件下递归里就不能单纯返回“找到的节点”了因为你必须区分两种情况一种是找到了答案一种是只找到了 p但 q 不在树里。我给出的方案是定义一个内部类记录搜索状态class Result { int foundCount; // 找到了几个目标节点 TreeNode candidate; // 当前认为的最近公共祖先 }每次递归合并左右子树的结果时先把 foundCount 相加再看 left 和 right 的 candidate 情况。只有当 foundCount 等于 2 时candidate 才是合法答案。说白了就是给递归函数增加一个计数器让返回值携带的信息更完整。这种写法在工程上比单个 TreeNode 引用可靠得多。还有另一种变体问题是给出每个节点的父节点数组然后让你找两个节点的公共祖先。这实际上把树退化成了一个“只能向上走”的有向图反而比二叉树递归更简单转化成上一节迭代解法里“从 p 向上标记再从 q 向上查”的思路就行。6.4 递归和非递归的选择权衡写递归代码时表达力很强逻辑紧凑缺点就是栈溢出隐患。写非递归代码时代码量上去了但更深层的问题能扛住。我个人的原则是树深明确小于一万层优先用递归代码更易读树深未知或者可能达到十万层就主动改成非递归。面试时最好把两种方案都准备一下因为面试官十有八九会接着问“如果树很深怎么办”。这正好也是热词里“快排非递归”这类问题背后的共同动机——递归和非递归不是好坏关系是取舍关系。6.5 和 Java 基础能力的关联还有人问过我做这题对 Java 本身有什么提升。答案是帮助很大。你会频繁使用对象引用比较、方法递归调用、HashMap、HashSet、Deque。理解和equals的区别、理解引用传递、理解递归调用栈这些正好是 Java 面试最爱问的基础点。所以别小看这样一道“算法题”它把不少 Java 八股文给串起来了。7. 写在最后的个人建议这道题我在不同阶段写过很多遍最大的体会是理解递归返回值比背模板重要得多。你真正想明白left和right到底代表什么之后就不需要靠记忆去写代码。每次写 LCA 之前我都会在纸上画一棵不超过 7 个节点的树手动把 p 和 q 放在不同位置然后沿着递归函数把返回值一步一步写出来。整个过程五分钟但效果比盲改十遍代码都好。如果你现在刷题容易卡壳我给你一个很笨但很有用的建议先照着上面的代码敲一遍再刻意删掉其中一行比如把root p || root q去掉跑一遍看结果错在哪。用这种“破坏性实验”去理解每一行代码的必要性是我觉得最不容易忘的方法。最后分享一个小技巧本地调试时把测试树打成一个扁平的字符串输出再配合递归日志比如打印每个节点访问顺序很快就能定位是逻辑问题还是树构造问题。这套方法不只在 Lc339 有用做其他二叉树题目同样见效。希望这篇能够帮你在“树 递归”这条路上少踩几个坑。 
长河君 · 2026/10/10 15:28:41 · 阅读 1.2k 二叉树最近公共祖先：Java递归解法详解与面试指南
做二叉树递归题很多人卡住的从来不是 Java 语法而是脑子里没有一棵树。Lc339 这道“二叉树的最近公共祖先”我觉得是最适合用来打通“树 递归”关节的题目解法只有十几行代码信息量却非常大。题目本身不绕给定一棵二叉树和两个节点 p、q找出它们距离最近的公共祖先节点。但真要把需求翻译成递归函数的返回值设计很多新手当场就懵了写完一跑要么空指针要么结果对不上。这篇文章我打算从读题、拆递归、写 Java 实现、构造测试、排查运行时错误一直写到面试变体尽量把每一步为什么这么做都讲透。如果你最近在准备 Java 面试或者刚学完二叉树遍历想找一道经典题练手这篇可以照着敲一遍。1. 把题面先拆干净Lc339 到底在考什么1.1 公共祖先的定义先说清楚公共祖先的定义是对于二叉树中的两个节点 p 和 q如果存在一个节点 x让 p 和 q 都出现在 x 的左子树或右子树中或者 p、q 本身就是一个节点比如 p 就是 x那么 x 就是 p 和 q 的公共祖先。注意“出现在子树中”这个说法它包含了节点本身。举个例子下面这棵树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4p5q1 时公共祖先是 3p5q4 时公共祖先是 5而不是 3p6q8 时公共祖先是 3。这里有个很多人第一次接触会忽略的细节一个节点可以成为自己的祖先。题目里说“最近公共祖先”其实就是所有公共祖先里离这两个节点最近的那一个也就是深度最大、最“低”的那个。p5q4 的情况下节点 5 既是 p 本身又包含了 q所以它比根节点 3 更近答案就是 5。1.2 三个容易忽略的题眼第一LeetCode 题面默认 p 和 q 都在这棵二叉树中而且 p 不等于 q。这是后面递归能写得那么简洁的前提。如果题目改成“节点可能不存在”代码就要复杂不少后面我会单独讲。第二二叉树的节点值在这个问题里并不一定全局唯一但题目会保证 p 和 q 是树中的真实节点引用。所以你在 Java 里可以用来比较节点对象而不是比较val。这一点很关键如果用node.val p.val去判断一旦树里出现重复值结果就很不可控。第三“最近”这个词决定了我们不能从根节点随便找一个公共祖先就结束要找的是最深的那个。所以递归顺序上很有讲究不能一上来就判断根节点必须先获取左右子树的信息再回到当前节点做判断。1.3 为什么这道题天然适合递归而不是迭代二叉树本身就是递归定义的一个节点由值和左右两个子树组成而左右子树仍然是二叉树。Java 里你写一个TreeNode它里面有left和right两个字段指向同类型的节点这种结构天生就适合用递归去处理。迭代当然也能做但思路会绕很多。比如你要记录每个节点的父节点然后从 p 向上走标记一串祖先再让 q 也向上走找到第一个被标记过的节点。这种解法要额外维护一个 Map 或者数组代码规模明显膨胀。而递归解法靠着函数调用栈天然就保留了一条从根到当前节点的路径我们要做的只是让每一层递归合理地向上“汇报”结果。还有一个隐藏考点这道题的结果依赖后序遍历。只有先把左子树和右子树都处理完才能判断当前节点是不是最近公共祖先。如果你按前序遍历“当前节点先判断再进子树”很容易提前返回拿到错误答案。这也是很多人写二叉树递归时最常犯的方向性错误。2. 递归思路自底向上汇报信息2.1 先想清楚递归函数返回什么写递归最忌讳的就是没想清楚返回值就开写。很多初学者把递归函数当成一个“黑盒”然后不断往里面塞参数最后代码越写越乱。Lc339 这个解法递归函数返回值的含义你可以这样定义如果当前子树里既没有 p也没有 q返回 null如果当前子树里找到了 p 或 q 中的某一个返回找到的那个节点如果当前子树里已经确定了最近公共祖先也返回这个祖先节点。最后这一点比较容易忽略。也就是说返回的非空节点有两种身份可能是“在我们还没确定答案的路径上它是 p 或 q”也可能是“在已经找到答案的分支上它就是答案本身”。一个返回值兼有两种含义这正是递归设计的精妙之处。这样设计的好处是我们不需要额外的标志位只要一个引用就能把信息从最底层一路带到最顶层。2.2 后序遍历的三段式写法递归函数的整体框架非常固定我建议直接背下来然后深入理解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;注意顺序一定是先递归左子树再递归右子树最后回到当前节点判断。这种先下后上的顺序就是后序遍历的核心。Java 代码里虽然只是三行但执行过程是完整的“左 - 右 - 根”路径。整个函数唯一的出口条件是if (root null || root p || root q) { return root; }root 为 null 说明这棵子树为空没找到任何目标节点root 是 p 或 q 说明当前节点就是一个目标节点我们直接把 root 返回上去。2.3 用一个小树完整走一遍还是用上面的树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4假设 p5q4。从根节点 3 开始递归进入左子树节点 5发现root p于是直接返回 5。这时候 5 的子树内部包括节点 4根本没有被遍历到。你可能会问那 q4 不就漏了吗实际上不会。因为 p 本身就是 q 的祖先如果 q 在 p 的子树里那 p 就是最深的那一层这个问题已经解决了不需要再往下找。接着右子树节点 1 往下递归从左到右遍历完所有节点发现既不是 p 也不是 q返回 null。所以回到根节点 3 时左子树返回值是 5右子树返回值是 null。此时判断left ! null right ! null不成立于是进入最后一行return left ! null ? left : right;返回 5。答案正确。再看另一个组合p6q8。根节点的左子树返回 6右子树返回 8。两边都不为 null说明 p 和 q 分别分布在当前节点的左右两侧当前节点 3 就是最近公共祖先直接返回 3。2.4 为什么提前返回不会错过“更近的祖先”这是面试里经常追问的点。回到第一种情况p5q4我们在节点 5 提前返回没有看它的子树为什么还知道答案是 5因为当 p 和 q 都在同一个子树里时最近公共祖先一定出现在那个子树里不会跑到当前节点“更上面”去。递归到节点 5 时p 已经找到了而 q 只可能在节点 5 的子树里。如果 q 真的在节点 5 的子树里那节点 5 就是它们共同的祖先并且比根节点 3 更低、更近。如果 q 不在节点 5 的子树里那么节点 5 并不会作为最近公共祖先它会继续向上返回直到某个更上层的节点发现左右子树分别各找到了一个目标节点。所以提前返回是安全的。这种“先局部、再整体”的思路本质上就是把问题拆给左右子树然后靠返回值的“引用”把信息一层层带上来。写熟了之后你会发现它能解决一大类树的递归问题。3. Java 代码实现从骨架到能跑起来3.1 TreeNode 定义和完整可运行代码先复习一下力扣风格的树节点定义public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }Lc339 的核心解法可以直接写在 Solution 类里class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 当前节点为空或者当前节点就是 p/q直接返回 if (root null || root p || root q) { return root; } // 去左子树找 p/q TreeNode left lowestCommonAncestor(root.left, p, q); // 去右子树找 p/q TreeNode right lowestCommonAncestor(root.right, p, q); // 左右子树各找到了一个说明当前节点就是公共祖先 if (left ! null right ! null) { return root; } // 哪边不为空就把哪边的结果向上传递 return left ! null ? left : right; } }代码就这么多可能不到二十行。很多题解里还会把最后一行写成return left null ? right : left;逻辑完全一样。我的建议是只用一种写法并且能说清楚它是在“向上传递非空的那一侧结果”。3.2 关键分支逐行拆解第一句是函数入口判断。root null是递归的自然出口一路递归到叶子节点的空孩子时触发。root p || root q是两个“提前命中”条件它保证了如果 p 出现在某个节点的左子树里那这个节点就会直接作为 left 的结果返回给上一层。第二段是左右子树递归调用。这里有一个很容易被忽视的细节无论左子树返回了什么右子树照常要递归。因为左子树找到 p 不代表右子树就没有 q最坏情况下你需要把整棵树都走一遍。我之前见过有新手在这里写TreeNode left lowestCommonAncestor(root.left, p, q); if (left ! null) return left;结果 p 和 q 分别在左右两侧时答案就错了。你直接返回 left根本不知道右子树还有 q。第三段判断左右返回值都不为空返回 root。这一步对应“p 和 q 当前分布在这个节点两侧”的情况也对应“左子树和右子树都已经各自找到了一个目标节点”的情况。最后一行是信息继续向上传递。如果 left 不为空说明左子树里找到了目标或者已经确定了答案right 为空说明右子树什么都没找到。这时候整个子树里唯一有意义的返回值就是 left所以把它交给上一层。这个传递过程会一直持续到最上层调用。3.3 Java 编码时的几个实用细节第一个细节判断节点是否相等用而不是equals()。在 LeetCode 这种在线判题环境里p 和 q 就是树里的同一个对象引用用对象地址比较又快又准确。如果你在本地自己构造测试树也要保证传入的 p、q 节点真的是树上挂着的节点而不是 new 一个值相同的节点。第二个细节提前处理 p 或 q 为 null 的情况。虽然题目默认不会传 null但工程上做防御性编程是习惯。如果 p、q 任意一个为 null递归里root p永远不会成立最后可能会返回一个不相关的节点或者抛出异常。最简单的做法是在接口入口加一层判断if (p null || q null) { return null; }第三个细节注意你的树节点构建。很多本地调试的运行时错误并不是算法写错了而是构造树的时候没有正确把左右子树连起来。比如你写了node.left a; node.right b;但 a 和 b 是自己 new 出来的并没有真的挂到 root 上那递归访问到一半就会遇到空指针。第四个细节不要试图在一个节点值重复的树上用val判断 p 和 q。前面说过力扣默认保证节点是唯一引用但你自己扩展成“传入两个 int 类型的 val”去找公共祖先时就必须改成遍历比较node.val pVal || node.val qVal并且要想好重复值会造成什么样的歧义。4. 复杂度、递归栈和“运行时错误”的真相4.1 时间复杂度和空间复杂度分析Lc339 的时间复杂度是 O(n)n 是二叉树的节点总数。原因很简单最坏情况下比如 p 和 q 都位于右子树的最深处递归会对大部分节点都访问一遍。每个节点最多被访问一次所以总时间是 O(n)。空间复杂度主要看递归栈的深度而不是整棵树的节点数。平衡二叉树下递归深度是 O(log n)最坏退化成一条链时深度是 O(n)。所以这道题的额外空间开销可以记为 O(height)height 是树高。你可以在面试里把这个结论说清楚面试官一般会顺着追问一句“如果这棵树特别深怎么办”这就引出了下面要说的栈溢出问题。4.2 为什么“写二叉树程序总是报运行时错误”这个词在初学者群里出镜率很高原因通常只有两类一类是 StackOverflowError另一类是 NullPointerException。StackOverflowError 十有八九是递归出口没写好。比如你忘记了root null这个条件递归就会在叶子节点的空子节点上继续无限往下调Java 的调用栈深度有限直接爆栈。还有一种情况是递归出口写了但树的深度太大。Java 默认线程栈大小通常在 512KB 到 1MB具体看 JVM 版本和操作系统。每个栈帧里保存了局部变量、返回值等信息深度到几万层左右就可能溢出。比如一棵深度为十万的退化二叉树用递归做 LCA跑不起来是正常的。算法没错限制在 Java 虚拟机层面。应对策略有两个第一种是调大 JVM 栈空间比如加-Xss10m这种办法在很多本地环境下有效但治标不治本第二种是改成迭代实现把递归栈换成自己手动维护的显式栈或哈希表。工程上真正遇到深度超大的场景我建议直接走迭代方案。NullPointerException 则通常出现在访问某个节点的 left 或 right 时这个节点本身是 null。比如你在递归里写了root.left.val这种代码但 root.left 为 null一运行就报错。这类问题和算法逻辑无关更多是树构造不完整导致的。4.3 非递归迭代解法作为备选这里给一个工程上更稳的非递归写法思路是先用一次遍历记录每个节点的父节点然后再从目标节点向上追溯。Java 里可以用 HashMap 存父节点引用public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { MapTreeNode, TreeNode parent new HashMap(); DequeTreeNode stack new ArrayDeque(); stack.push(root); parent.put(root, null); // 用迭代遍历把整棵树的父节点关系记录下来 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); } } // 从 p 向上走把所有祖先加入集合 SetTreeNode ancestors new HashSet(); while (p ! null) { ancestors.add(p); p parent.get(p); } // 从 q 向上走遇到的第一个在集合里的节点就是 LCA while (!ancestors.contains(q)) { q parent.get(q); } return q; }这个写法的时间复杂度还是 O(n)空间复杂度是 O(n)优点是不受递归栈深度限制。缺点是代码明显更啰嗦而且用 HashMap 存引用在极端情况下内存占用会偏高。面试里我不建议大家上来就甩这种写法可以先讲递归再补充一句“如果树特别深我也可以改成迭代式”。5. 测试用例与排错实录5.1 自己构造一棵测试树写算法题最怕的是只在脑子里空想。我的习惯是在本地 main 方法里把树搭出来然后调用接口打印结果。以第一节那棵树为例public class Lc339Test { public static void main(String[] args) { // 构造节点 TreeNode root new TreeNode(3); TreeNode node5 new TreeNode(5); TreeNode node1 new TreeNode(1); TreeNode node6 new TreeNode(6); TreeNode node2 new TreeNode(2); TreeNode node0 new TreeNode(0); TreeNode node8 new TreeNode(8); TreeNode node7 new TreeNode(7); TreeNode node4 new TreeNode(4); // 连接左右子树 root.left node5; root.right node1; node5.left node6; node5.right node2; node1.left node0; node1.right node8; node2.left node7; node2.right node4; Solution solution new Solution(); TreeNode ans solution.lowestCommonAncestor(root, node6, node8); System.out.println(ans null ? null : ans.val); // 期望输出 3 } }这里的核心点是传入的 p 和 q 必须是用 root.left、root.right 等引用串起来的节点。如果你图省事再new TreeNode(6)一个出来虽然 val 相同但对象引用不同用判断永远也匹配不上。5.2 我平时跑 LCA 用的测试用例清单下面这组用例基本能把边界情况覆盖住建议按顺序跑pq期望输出测试意图节点5节点13左右各一个目标公共祖先是根节点5节点45一个目标是另一个祖先的子树验证提前返回节点6节点83两个目标在不同分支根节点3节点63p 本身就是公共祖先节点7节点42目标在更深的子树内null树的root无null空树边界情况拿到代码第一时间跑第一行和第三行可以先确认大体逻辑对。第二行是最容易出错的如果结果输出了 3说明你的递归逻辑写反了或者提前返回写错了。我之前给别人 review 代码时发现有人把root p || root q这个条件写在递归调用之后判断导致答案永远是根节点原因就是没有理解“自身就是祖先”这个定义。5.3 一个典型的 StackOverflowError 调试过程假设你在一个特别深的测试用例上报了 StackOverflowError。不要慌先看异常堆栈最顶部它会明确指向递归函数里某个具体行。然后用排除法第一步检查递归出口。如果你的函数里没有写if (root null) return null;那在叶子节点的空孩子上就会无限递归。这种情况最常见代码里补上这个出口就行。第二步判断是不是树本身退化成了单链表。比如所有节点都只有右孩子那递归深度就是节点总数。你可以在本地用一个小规模退化树跑一下比如 5000 个节点如果还报 StackOverflowError说明问题确实出在深度上。第三步尝试调大栈空间或者换成迭代解法。调大 JVM 栈可以快速验证思路但不能作为最终答案提交。我建议把上一节那个迭代写法的测试用例跑一遍确认结果一致以后面对这种输入就有底了。我还在调试时习惯在递归函数里加一行临时输出System.out.println(visit: (root null ? null : root.val));跑完一遍你就能看到递归实际访问的节点顺序。排查结束后记得删掉这些输出不然放在大树上会打出海量日志本末倒置。6. 面试追问与变体扩展6.1 从这道题引申出来的二叉树高频题Lc339 不是孤立的一道题。它的方方面面都能和“二叉树的遍历”“二叉树的深度”“搜索二叉树”“线索二叉树”这些关键词搭上关系。先说二叉树的遍历。Lc339 表面上是找公共祖先实际应用的是后序遍历只是返回值从 void 变成了 TreeNode。如果你把先序、中序、后序遍历的递归结构练得很熟这道题你只看一眼代码结构就能反应过来。再说二叉树的深度。求二叉树最大深度的递归代码也是自底向上max(maxDepth(root.left), maxDepth(root.right)) 1。这和 Lc339 的“先递归子树再处理当前节点”有着完全一样的骨架。把这两道题放一起做相互验证理解会深很多。至于线索二叉树虽然它的核心是把空指针利用起来实现中序线索遍历但它的节点定义和递归遍历思路和普通二叉树是相通的。理解普通二叉树的左右子树递归关系后看线索二叉树会轻松很多。6.2 如果是搜索二叉树代码可以更快如果题目给的不是普通二叉树而是二叉搜索树BST那我们可以充分利用左子树所有节点值都小于根、右子树所有节点值都大于根的特点把递归优化成单路径查找。Java 可以这样写public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) { while (root ! null) { if (p.val root.val q.val root.val) { // p 和 q 都在左子树 root root.left; } else if (p.val root.val q.val root.val) { // p 和 q 都在右子树 root root.right; } else { // 当前节点在 p 和 q 的中间或者当前节点就是 p/q return root; } } return null; }这段代码的时间复杂度最坏是 O(n)平均表现是 O(log n)空间复杂度 O(1)。和通用递归解法的最大区别是它不需要遍历整棵树只沿着一条分支往下走。面试时如果你能先给出通用解法再补充“如果题目改成了搜索二叉树我还能优化成迭代”这会是明显的加分项。6.3 更复杂的变体p 或 q 可能不存在很多厂商面试不会只满足于默写代码。最常见的追问是把条件改成“p 和 q 不一定存在于树中找到它们的最近公共祖先如果不存在就返回 null”。这个条件下递归里就不能单纯返回“找到的节点”了因为你必须区分两种情况一种是找到了答案一种是只找到了 p但 q 不在树里。我给出的方案是定义一个内部类记录搜索状态class Result { int foundCount; // 找到了几个目标节点 TreeNode candidate; // 当前认为的最近公共祖先 }每次递归合并左右子树的结果时先把 foundCount 相加再看 left 和 right 的 candidate 情况。只有当 foundCount 等于 2 时candidate 才是合法答案。说白了就是给递归函数增加一个计数器让返回值携带的信息更完整。这种写法在工程上比单个 TreeNode 引用可靠得多。还有另一种变体问题是给出每个节点的父节点数组然后让你找两个节点的公共祖先。这实际上把树退化成了一个“只能向上走”的有向图反而比二叉树递归更简单转化成上一节迭代解法里“从 p 向上标记再从 q 向上查”的思路就行。6.4 递归和非递归的选择权衡写递归代码时表达力很强逻辑紧凑缺点就是栈溢出隐患。写非递归代码时代码量上去了但更深层的问题能扛住。我个人的原则是树深明确小于一万层优先用递归代码更易读树深未知或者可能达到十万层就主动改成非递归。面试时最好把两种方案都准备一下因为面试官十有八九会接着问“如果树很深怎么办”。这正好也是热词里“快排非递归”这类问题背后的共同动机——递归和非递归不是好坏关系是取舍关系。6.5 和 Java 基础能力的关联还有人问过我做这题对 Java 本身有什么提升。答案是帮助很大。你会频繁使用对象引用比较、方法递归调用、HashMap、HashSet、Deque。理解和equals的区别、理解引用传递、理解递归调用栈这些正好是 Java 面试最爱问的基础点。所以别小看这样一道“算法题”它把不少 Java 八股文给串起来了。7. 写在最后的个人建议这道题我在不同阶段写过很多遍最大的体会是理解递归返回值比背模板重要得多。你真正想明白left和right到底代表什么之后就不需要靠记忆去写代码。每次写 LCA 之前我都会在纸上画一棵不超过 7 个节点的树手动把 p 和 q 放在不同位置然后沿着递归函数把返回值一步一步写出来。整个过程五分钟但效果比盲改十遍代码都好。如果你现在刷题容易卡壳我给你一个很笨但很有用的建议先照着上面的代码敲一遍再刻意删掉其中一行比如把root p || root q去掉跑一遍看结果错在哪。用这种“破坏性实验”去理解每一行代码的必要性是我觉得最不容易忘的方法。最后分享一个小技巧本地调试时把测试树打成一个扁平的字符串输出再配合递归日志比如打印每个节点访问顺序很快就能定位是逻辑问题还是树构造问题。这套方法不只在 Lc339 有用做其他二叉树题目同样见效。希望这篇能够帮你在“树 递归”这条路上少踩几个坑。