LeetCode 1644. 二叉树的最近公共祖先 II

2024-11-13 HGNULB 约 9 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1644. 二叉树的最近公共祖先 II

题意分析

给一棵二叉树的根节点和两个节点 p、q，返回它们最深的公共祖先。与 236 的差别只有一句话：p 和 q 不保证在树中存在，只要有一个不在，就必须返回 null。

这一句话改变的东西比看上去多。236 之所以能写成「碰到 p 或 q 就立刻返回、不再往下走」，靠的是「两个节点一定都在树里」这个前提——一旦提前返回，剩下那一半子树没搜也不影响结论。前提没了，提前返回就等于放弃了确认「另一个节点到底在不在」的机会。

所以这题实际上是两个目标叠在同一趟遍历里：一是找出最深的公共祖先位置，二是确认两个节点都真实存在。前者只需要局部信息（子树里有没有），后者需要全局信息（整棵树里有没有），两者对遍历完整度的要求不同。

节点值题目保证互不相同，但比较时按节点引用比更稳妥，因为传进来的 p、q 就是树里的节点对象。

边界包括：p 和 q 都不在树中；只有一个在；p 是 q 的祖先（此时答案是 p 本身）；p 与 q 是同一个节点；以及根节点就是其中之一。

解法：DFS 返回 LCA + 存在性校验

核心思路

暴力做法是先跑两趟遍历确认 p、q 是否存在，存在再套 236 的模板跑第三趟，$O(n)$ 时间但常数是三倍，而且代码里有三段几乎一样的遍历。瓶颈在于「存在性」和「祖先位置」被拆成了两件事，实际上它们可以在同一趟后序遍历里同时完成。

关键观察是：保留 236 的合并逻辑，但命中目标时不能提前返回。必须先遍历左右子树，再判断当前节点是不是 p 或 q，这样既能计算 LCA 候选，也能完整确认两个目标是否存在。

递归函数 dfs(node) 的返回值定义为：若 node 子树中同时含有 p 和 q，返回它们在该子树中的最近公共祖先；若只含其中一个，返回那一个；若都不含，返回 null。注意这个定义在 p、q 不存在时依然自洽——「都不含」这一支会一路把 null 传上去。

Java 在入口创建局部布尔数组 found[2]，Go 用闭包捕获两个局部布尔值；命中 p、q 时分别置真。状态属于本次调用，不放在对象字段里，因此连续调用同一个 Solution 也不会继承旧结果。

后序归纳可证明候选正确：左右子树各自返回其内部的目标或 LCA；两侧都非空时当前节点是首次汇合点，当前节点本身命中目标时它必然是另一目标的祖先，否则上传唯一非空结果。遍历结束后，只有两个存在标记都为真，候选才是有效答案。

解题步骤

空节点返回 null。这是递归的地基，也让「子树中不含目标」这一支有了统一的表示。

先递归左子树，再递归右子树，最后才处理当前节点。顺序必须是后序：只有把两侧都走完，才能保证 foundP、foundQ 覆盖整棵树；一旦在前序位置命中目标就 return，下方子树被整片跳过，存在性统计立刻失真。

在后序位置更新两个存在标记。使用引用相等 node == p，不依赖节点值；若 p == q，同一个节点会同时点亮两个标记，仍能正确返回自身。

合并候选。若当前节点就是 p 或 q，返回当前节点；否则左右结果都非空时返回当前节点，仅一侧非空时上传那一侧，两侧都空时返回 null。

回到入口做最终裁决：foundP && foundQ 为真才返回递归结果，否则返回 null。这一步不能省，也不能提前到递归内部——存在性是全局结论，只有遍历结束才成立。

以这棵树走一遍：根 3，左子树是 5（左 6，右 2），右子树是 1（左 0，右 8）。取 p = 5、q = 4，其中 4 不在树中。

后序访问到节点 5 时命中 p，设置 foundP 并返回节点 5；其余子树都找不到目标，候选 5 一路上传到根。因此 dfs(root) 的候选看起来是 5。

但遍历结束时 foundQ 仍是假，入口最终返回 null。若改成 p = 5、q = 6，由于 DFS 先走完节点 5 的子树，两个标记都为真，节点 5 作为祖先返回；这正是不能在命中 5 时提前结束的原因。

代码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean[] found = new boolean[2];
        TreeNode candidate = dfs(root, p, q, found);
        return found[0] && found[1] ? candidate : null;
    }

    private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q, boolean[] found) {
        if (node == null) {
            return null;
        }
        TreeNode left = dfs(node.left, p, q, found);
        TreeNode right = dfs(node.right, p, q, found);

        if (node == p) {
            found[0] = true;
        }
        if (node == q) {
            found[1] = true;
        }
        if (node == p || node == q) {
            return node;
        }
        if (left != null && right != null) {
            return node;
        }
        return left != null ? left : right;
    }
}

func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
	foundP, foundQ := false, false

	var dfs func(node *TreeNode) *TreeNode
	dfs = func(node *TreeNode) *TreeNode {
		if node == nil {
			return nil
		}
		left := dfs(node.Left)
		right := dfs(node.Right)

		if node == p {
			foundP = true
		}
		if node == q {
			foundQ = true
		}

		if node == p || node == q {
			return node
		}
		if left != nil && right != nil {
			return node
		}
		if left != nil {
			return left
		}
		return right
	}

	res := dfs(root)
	if foundP && foundQ {
		return res
	}
	return nil
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为节点数。后序遍历访问每个节点恰好一次，节点内部只做常数次引用比较与分支判断，没有任何提前退出也没有重复访问。

空间复杂度：$O(h)$，h 为树高，来自递归调用栈；平衡树为 $O(\log n)$，退化树为 $O(n)$。存在性状态只占常数空间。

关键点总结

「目标可能不存在」是 LCA 家族的核心变式信号，它直接否决了 236 的提前返回优化，必须换成全树遍历。识别这个信号比记住模板更重要。

把「位置」和「合法性」拆成两个信息通道：递归返回值负责候选位置，本次调用的局部布尔状态负责存在性，最后在入口合并。

后序位置是「需要子树信息才能决策」的标志。本题把目标判定放到后序，纯粹是为了保证遍历完整，这是一个值得记住的调整手法。

递归返回值的语义要写死并全程遵守：本题定义为「子树内含有的目标或它们的 LCA」，任何一层偏离这个定义都会破坏上层合并逻辑。

用引用比较而非值比较，既贴合题目给的是节点对象这一事实，也在节点值可能重复的变式里天然正确。

调用级状态不要留在 Solution 字段中；局部数组或闭包捕获可让连续调用彼此隔离，不需要依赖手动重置。

面试视角：先主动指出「和 236 的唯一差别是不保证存在」，再解释「所以不能提前返回」，然后给出一趟后序遍历同时完成两件事的方案。面试官常追问「为什么不先跑两趟确认存在性」，答案是三趟遍历同为 $O(n)$ 但常数更差、代码更长；再追问「如果要求返回 p、q 分别是否存在」，只要把两个布尔量暴露出去即可，说明这个设计是可扩展的。

易错点总结

错误写法：照抄 236，在递归开头写 if (node == p || node == q) return node;。用例：树为 3 → 左 5 → 左 6，p = 5、q = 6 → 访问到 5 立即返回，节点 6 从未被访问，foundQ 为假，最终返回 null，正确答案是节点 5。

错误写法：最终判断写成 foundP || foundQ。用例：树为 3 → 左 5 → 左 6，p = 5、q 是不在树中的节点 → foundP 为真使条件成立，返回节点 5，正确答案是 null。

错误写法：合并时只判断左右结果，忘记当前节点也可能是目标。树为 3 → 左 5 → 左 6，p = 5、q = 6 时，若节点 5 直接上传左侧结果 6，最终会错误返回 6；当前节点命中目标时应返回自身。

错误写法：最后返回 res 而不判 foundP && foundQ。用例：树为单节点 1，p = 1、q 是一个不在树中的节点 → dfs 返回节点 1，直接返回它，正确答案是 null。

错误写法：用节点值代替引用比较。若 q 是不在树中的新节点、但值恰好与树内某节点相同，值比较会把它误判为存在并返回非空答案；应直接比较 node == q。

错误写法：漏掉 node == null 的递归基。用例：任意树的叶子节点 → 递归下探到空孩子时访问 node.left 触发空指针异常。

错误写法：foundP / foundQ 声明成方法内的局部变量再传值给递归。用例：树为 3 → 左 5 → 左 6，p = 5、q = 6 → Java 中基本类型按值传递，深层递归里的赋值不会反映到调用方，两个标记恒为假，永远返回 null。

错误写法：p 与 q 是同一个节点时，只用一个标记记录「找到了目标」并要求计数达到 2。用例：树为单节点 1，p = q = 1 → 计数只会加到 1，返回 null，而正确答案是节点 1，因为一个节点是它自己的祖先。

错误写法：把 foundP、foundQ 存为成员变量且入口不重置。同一个 Solution 第一次查询两点都存在、第二次查询缺失节点时，旧标记仍为真，第二次可能错误返回非空候选。

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	保证两点都存在，因此可以碰到目标就提前返回，是本题去掉存在性校验后的形态
235. 二叉搜索树的最近公共祖先	中等	有序性把递归换成一路比较值大小的下探，$O(h)$ 且无需回溯
1650. 二叉树的最近公共祖先 III	中等	拿不到根但每个节点有 `parent`，转成两条链表求交点，$O(1)$ 额外空间
1676. 二叉树的最近公共祖先 IV	中等	目标从两个扩展到一组，用集合判定命中，但保证全部存在，反而比本题简单
1123. 最深叶节点的最近公共祖先	中等	目标集合不是给定的而要自己求出，递归需同时返回子树深度与 LCA
1483. 树节点的第 K 个祖先	困难	多次查询下需要倍增预处理，是把祖先问题从单次遍历升级为可重复查询的数据结构
剑指 Offer 68 - II. 二叉树的最近公共祖先	简单	与 236 同题，可直接套用提前返回的精简模板
面试题 04.08. 首个共同祖先	中等	与 236 同题，面试中常被要求额外说明节点不存在时该如何补救