LeetCode 1214. 查找两棵二叉搜索树之和

2021-11-03 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等未解决会员题 1-2 微软

题目描述

✅ 1214. 查找两棵二叉搜索树之和

题意分析

给定两棵二叉搜索树和目标和 target，判断能否从第一棵树选一个节点、从第二棵树再选一个节点，使两者的值相加等于目标。

两个节点必须分别来自两棵树，不能在同一棵树里随便选两个。只要求返回是否存在，不统计配对数，也不需要返回节点；相同数值分别出现在两棵树时，同样可以构成合法配对。

解法：哈希集合 + DFS

核心思路

[!blue]

若第二棵树当前节点值为 v，能与它配对的第一棵树节点值就唯一确定为 target - v。因此可以先把第一棵树的所有值收集到哈希集合，再遍历第二棵树查询补数，避免为每个节点重新扫描另一整棵树。

第一阶段的 collect 只负责完整记录第一棵树。重复值在集合中合并没有影响，因为本题查询的是某个值是否存在，而不是有多少种配对。空节点不提供任何值，直接结束该分支。

第二阶段的 exists 返回当前子树里是否有节点能与集合中的值配对。先查询当前节点的补数，命中就返回真；否则递归左右子树，用逻辑或合并结果，任意一侧成功即可。两侧都没有配对才返回假，空节点也返回假。

集合始终来自第一棵树，被查询的节点始终来自第二棵树，来源限制由这两个阶段自然保证。全部合法配对的第二个节点都会被检查，因此不会漏掉答案；每次命中又都能在第一棵树中找到真实补数，所以不会误用同树内的节点。

这套方法使用的是哈希存在性查询，不依赖二叉搜索树的有序遍历顺序。代码也不修改原树，并使用宽整数计算补数，避免减法在较窄类型中先发生溢出。

解题步骤

创建空集合，DFS 遍历第一棵树并加入全部节点值。

从第二棵树根开始查询，空节点返回假。

若集合包含 target - 当前值，立即返回真。

否则查询左右子树，任一子树命中就短路返回真；全部未命中则返回假。

代码实现

// 先把树1的值全收进集合，再遍历树2逐点查补值。
class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        // 集合只收第一棵树，保证配对来自不同的树。
        Set<Long> set = new HashSet<>();

        collect(root1, set);

        return exists(root2, set, target);
    }

    // 将当前子树全部值加入集合，不改变原树。
    private void collect(TreeNode node, Set<Long> set) {
        if (node == null) {
            return;
        }

        set.add((long) node.val);
        collect(node.left, set);
        collect(node.right, set);
    }

    // 返回当前子树是否有节点能与第一棵树中的值配对。
    private boolean exists(TreeNode node, Set<Long> set, int target) {
        if (node == null) {
            return false;
        }

        // 当前节点来自第二棵树，查询第一棵树中是否有补数。
        if (set.contains((long) target - node.val)) {
            return true;
        }

        // 任一侧命中就结束，短路或避免继续搜索无关分支。
        return exists(node.left, set, target) || exists(node.right, set, target);
    }
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
    // 集合只收第一棵树，保证配对来自不同的树。
    set := make(map[int64]struct{})
    collect(root1, set)
    return exists(root2, set, target)
}

// 将当前子树全部值加入集合，不改变原树。
func collect(node *TreeNode, set map[int64]struct{}) {
    if node == nil {
        return
    }
    set[int64(node.Val)] = struct{}{}
    collect(node.Left, set)
    collect(node.Right, set)
}

// 返回当前子树是否有节点能与第一棵树中的值配对。
func exists(node *TreeNode, set map[int64]struct{}, target int) bool {
    if node == nil {
        return false
    }
    // 当前节点来自第二棵树，查询第一棵树中是否有补数。
    if _, ok := set[int64(target)-int64(node.Val)]; ok {
        return true
    }
    // 任一侧命中就结束，短路或避免继续搜索无关分支。
    return exists(node.Left, set, target) || exists(node.Right, set, target)
}

复杂度分析

时间复杂度：期望 $O(n+m)$，其中 n、m 是两树节点数。第一棵树完整访问一次，第二棵树至多访问一次，每个查询期望为常量时间。

空间复杂度：$O(n+\max(h_1,h_2))$，集合最多保存第一棵树的 n 个值；两次 DFS 先后执行，调用栈取两树高度中的较大者。

关键点总结

[!green]

固定第二棵树的一个值后，只需查询第一棵树中唯一的补数。

两棵树角色分离，天然保证配对来源，不必额外排除同一节点。

存在性问题可以使用集合去重，并在第一次命中后立即结束。

易错点总结

[!yellow]

把两棵树的值先混合，再做普通两数之和，可能误选同一棵树里的两个节点。

补数写成 v - target，会改变原来的加法等式，正确方向是 target - v。

空节点返回真，会让任何没有匹配的搜索最终在空孩子处误判成功。

用逻辑与合并左右子树，等于要求两侧都出现配对，本题只需要任意一侧成功。

仅凭当前值大于目标就剪枝并不可靠，另一棵树的负数仍可能与它组成目标和。

相似题目

题目	难度	关联与区别
653. 两数之和 IV - 输入二叉搜索树	简单	原题从同一棵BST找两个节点，本题要求两棵树各选一个，候选来源不能混淆。
173. 二叉搜索树迭代器	中等	可用一棵树的升序迭代器和另一棵树的降序迭代器，像有序双指针一样寻找目标和。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/87618762

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