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

2024-11-13 HGNULB 约 5 分钟

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

分类

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

题目描述

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

题意分析

求目标节点 p、q 的最近公共祖先，但两个目标可能不都在树中。只要缺少一个就必须返回空，因此既要计算祖先候选，也要确认两个节点实际出现过。

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

核心思路

[!blue]
递归返回值描述当前子树的查找结果：没有目标时返回空，只找到一个时返回该目标，两个都找到时返回它们在这棵子树中的最近公共祖先。同时用两个共享标记，记录本次遍历是否真正遇到 p、q；节点按引用或指针身份比较。

先递归左右孩子，再合并结果。若当前节点就是某个目标，返回当前节点：另一个目标若在它的后代中，当前节点本身就是最近公共祖先；若不在这棵子树中，它仍是需要向上传递的单个目标。

当前节点不是目标时，左右结果都非空，说明两目标分别位于两侧，当前节点就是最低的汇合位置；只有一侧非空，则把那一侧的结果继续上传；两侧都为空则返回空。

即使当前节点是目标，也必须先遍历后代，否则会漏记位于下方的另一个目标。整棵树遍历结束后，只有两个存在标记都为真，才能把候选作为答案；一个标记为假时，即使候选非空也要返回空。标记在每次入口调用中重新创建，避免多次查询互相影响。

解题步骤

每次调用创建独立的存在标记。

后序遍历，空节点返回空。

按节点身份记录命中情况，合并左右候选。

回到入口，两目标都存在才返回候选。

代码实现

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)$，遍历全部节点。

空间复杂度：$O(h+1)$，递归栈由树高决定，存在标记为常数空间。

关键点总结

[!green]

候选非空不代表两目标都存在。

当前目标也可能是另一个目标的祖先。

状态属于本次调用，避免旧查询结果残留。

易错点总结

[!yellow]

遇到目标就提前返回：其下方的另一个目标可能未被发现。

只要求一个存在标记为真：缺失目标时仍可能返回非空候选。

忽略当前节点也是目标：祖孙目标场景可能错误上传后代。

Java 用布尔值传参后期望递归改写外层值：基本类型按值传递，需使用当前的共享数组。

相似题目

题目	难度	关联与区别
236. 二叉树的最近公共祖先	中等	原题保证两个目标都存在，本题可能缺失，不能命中一个节点就直接当作完整答案返回。
1676. 二叉树的最近公共祖先 IV	中等	原题推广为多个已知目标，本题仍是两个目标但需额外确认存在性，契约不同。

转载与许可

作者 HGNULB

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

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