LeetCode 1676. 二叉树的最近公共祖先 IV

2024-11-13 HGNULB 约 4 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决会员题 1-2 字节

题目描述

✅ 1676. 二叉树的最近公共祖先 IV

题意分析

给定二叉树和一组目标节点，求能够覆盖全部目标的最深祖先。节点也视为自己的祖先，因此答案可能就是某个目标节点。目标集合非空，题目保证所有目标都存在于树中。

解法：目标集合 + 后序计数

核心思路

[!blue]
把“是否覆盖全部目标”转成子树计数。 用集合 targets 保存目标节点，need 为目标总数。定义 countTargets(node) 返回以 node 为根的子树内有多少个目标，空子树返回 0。

左子树、右子树和当前节点互不重叠，所以子树目标数等于左右计数之和，再加上当前节点属于目标集合时的 1。计算当前计数需要孩子的结果，因此使用后序遍历。

当 found == need 时，当前子树包含所有目标，当前节点就是一个共同祖先。所有共同祖先位于同一条向根延伸的祖先链上；后序会先处理这条链上更低的节点，所以第一次计数达到 need 的节点就是最近公共祖先。之后计数仍会向上传递，但不能覆盖已经找到的答案。

解题步骤

建立目标节点集合并记录 need，初始化答案为空。

空节点返回 0；非空节点先递归得到左右子树的目标数。

将左右计数相加，若当前节点也是目标，再加 1。

若计数等于 need 且答案尚为空，记录当前节点；随后返回计数供父节点使用。

只有一个目标时，它自己的计数首次达到 1，答案就是它。目标之间有祖孙关系时，当前节点的贡献不能遗漏；目标分散在两侧时，必须合并两边的数量后才能判定。集合保存节点本身，Java 按节点对象、Go 按节点指针查询目标身份。

代码实现

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)$，建立 k 个目标的集合并遍历 n 个树节点。

空间复杂度：$O(k+h)$，目标集合和递归栈。

关键点总结

[!green]

计数包含当前节点自身。

只有包含全部目标才是共同祖先。

后序第一次命中保留最深答案。

易错点总结

[!yellow]

每次计数满足就覆盖答案：结果会被更高祖先一路覆盖到根。

当前节点属于目标却不计数：祖孙目标可能无法满足总数。

只判断某个子树有目标：不能保证它包含全部目标。

相似题目

题目	难度	关联与区别
236. 二叉树的最近公共祖先	中等	把两个目标扩展成目标集合，后序合并命中信息寻找共同祖先。
1644. 二叉树的最近公共祖先 II	中等	原题目标可能不存在，本题按给定目标都在树中的契约处理，不能混淆存在性要求。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/97486679

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！