LeetCode 1676. 二叉树的最近公共祖先 IV
目录
题目描述
题意分析
给定二叉树的根节点和一个节点数组
nodes，返回这些节点的最近公共祖先。与 236 的差别只有一处：目标从两个变成了任意多个。题目给了两条重要保证：
nodes中的所有节点都存在于树中，而且树中所有节点的值互不相同。前者意味着不需要像 1644 那样额外校验存在性，可以放心地提前返回；后者让「判断当前节点是不是目标之一」可以用值或引用任一方式实现，不会歧义。
nodes的长度至少为 1。只有一个目标时，答案就是它自己——一个节点是它自己的祖先。这个退化情况必须被主逻辑自然覆盖。「多个目标的最近公共祖先」这个概念本身要先想明白：它是所有目标的公共祖先中深度最大的那个。等价的刻画是——从这个节点的子树里能找到
nodes中的全部节点，而它的任何一个孩子的子树都做不到。由此可以推出一条对写代码很有用的性质：如果某个目标节点本身是其他目标的祖先，那么答案就是它。因为它已经把那些后代都装在自己的子树里了，再往下就装不全。
边界包括：
nodes只有一个元素；nodes中某个元素就是根节点（答案必是根）；nodes中存在祖孙关系；以及nodes中的元素分散在树的各个角落。
解法：目标集合 + DFS
核心思路
把目标节点引用放入哈希集合。后序 DFS 让每个节点返回一个明确的量：
count(node)表示node子树中包含多少个目标节点。若目标总数为
need，一个节点是所有目标的公共祖先，当且仅当count(node) == need。所有满足条件的节点沿祖先链向上分布，其中最深的那个就是最近公共祖先。因此在后序位置计算
\[found = count(node.left) + count(node.right) + [node \text{ 是目标}]\]第一次遇到
found == need的节点就记录为答案。后序遍历保证孩子先于父亲被检查，所以这个“第一次”一定是包含全部目标的最深节点。循环不变量是：
count返回前，左右子树的目标数已经准确；answer若已设置，就是目前后序访问到的、包含全部目标的最深节点。目标全部存在于树中，所以根节点的计数最终必为need，答案一定能找到。
解题步骤
- 将
nodes放入按节点引用比较的集合，need取集合大小。- 后序递归左右子树，取得
leftCount与rightCount。- 当前节点若属于目标集合，再加 1，得到整棵当前子树的
found。- 若
found == need且答案尚未记录，把当前节点记为答案。- 返回
found给父节点，入口最终返回记录的答案。在经典树
3(5,1)中，若目标为节点 7 和 4，它们在节点 2 的左右两侧：节点 2 首次得到计数 2，因此答案是 2。若目标为节点 5 和其后代 4，节点 5 的计数包含自身和后代，答案自然是 5。单个目标时，目标节点自身首次得到计数 1；目标包含根时，只有根能统计到全部目标。两种边界都无需特判。
代码实现
import java.util.HashSet;
import java.util.Set;
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
Set<TreeNode> targets = new HashSet<>();
for (TreeNode node : nodes) {
targets.add(node);
}
TreeNode[] answer = new TreeNode[1];
countTargets(root, targets, targets.size(), answer);
return answer[0];
}
private int countTargets(
TreeNode node, Set<TreeNode> targets, int need, TreeNode[] answer) {
if (node == null) {
return 0;
}
int found = countTargets(node.left, targets, need, answer)
+ countTargets(node.right, targets, need, answer);
if (targets.contains(node)) {
found++;
}
if (answer[0] == null && found == need) {
answer[0] = node;
}
return found;
}
}
func lowestCommonAncestor(root *TreeNode, nodes []*TreeNode) *TreeNode {
targets := make(map[*TreeNode]struct{}, len(nodes))
for _, node := range nodes {
targets[node] = struct{}{}
}
need := len(targets)
var answer *TreeNode
var countTargets func(*TreeNode) int
countTargets = func(node *TreeNode) int {
if node == nil {
return 0
}
found := countTargets(node.Left) + countTargets(node.Right)
if _, ok := targets[node]; ok {
found++
}
if answer == nil && found == need {
answer = node
}
return found
}
countTargets(root)
return answer
}
复杂度分析
- 时间复杂度：$O(n+k)$。建立目标集合需要 $O(k)$，后序遍历每个树节点一次。
- 空间复杂度：$O(k+h)$。集合保存 $k$ 个目标，递归栈深度为树高 $h$；退化树中 $h=O(n)$。
关键点总结
count(node)的语义固定为当前子树中的目标数量，后序顺序才能先得到完整子树信息。- “包含全部目标”的节点可能有多个，后序第一次命中的最深节点才是 LCA。
- 当前节点本身是目标时也要计数，这会自然覆盖目标之间的祖孙关系。
- 集合使用节点引用，不依赖节点值唯一这一额外条件。
- 题目保证所有目标存在；若去掉该保证，应检查根节点最终计数是否等于
need。
易错点总结
- 在递归左右孩子之前判断
found == need：子树尚未统计完整，会漏掉分散在后代的目标。- 当前节点是目标却不加 1：目标包含某个祖先时计数不足，例如目标为节点 5 和其后代 4。
- 每次满足条件都覆盖答案：会从真正 LCA 一路覆盖到根；只记录后序第一次命中。
- 用节点值而非引用建集合：若扩展到允许重复值的树，会把非目标节点误计入。
- 单个目标特判为根节点：一个节点的 LCA 是它自己，主逻辑已经覆盖。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 236. 二叉树的最近公共祖先 | 中等 | 目标固定为两个的原型，本题的递归骨架完全照搬自它 |
| 235. 二叉搜索树的最近公共祖先 | 中等 | 借有序性一路下探，无需回溯也无需集合，$O(h)$ 完成 |
| 1644. 二叉树的最近公共祖先 II | 中等 | 目标可能不存在，必须放弃提前返回、改用后序遍历统计存在性 |
| 1650. 二叉树的最近公共祖先 III | 中等 | 无根有父指针，转成两条链表求交点，用双指针做到 $O(1)$ 空间 |
| 1123. 最深叶节点的最近公共祖先 | 中等 | 目标集合需要自己推导（最深的那批叶子），递归要同时返回深度与祖先 |
| 1026. 节点与其祖先之间的最大差值 | 中等 | 同样在递归中沿路径传递信息，但传的是极值区间而非节点引用 |
| 1483. 树节点的第 K 个祖先 | 困难 | 面向多次查询，需要倍增预处理，把单次 $O(h)$ 降为 $O(\log h)$ |
| 剑指 Offer 68 - II. 二叉树的最近公共祖先 | 简单 | 与 236 同题，适合先在这里把提前返回的写法练熟再来做本题的推广 |