LeetCode 653. 两数之和 IV - 输入二叉搜索树

2025-04-21 HGNULB 约 11 分钟

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

分类

题目描述

✅ 653. 两数之和 IV - 输入二叉搜索树

题意分析

给一棵二叉搜索树的根节点和一个整数 k，判断树中是否存在两个不同的节点，它们的值之和等于 k。只要返回布尔值，不需要给出是哪两个节点。

要什么：存在性判定。这一点决定了我们一旦找到答案就可以立刻短路返回，不必遍历完整棵树。

「两个不同的节点」是本题最容易被忽略的约束。它禁止的是同一个节点被用两次（比如 k = 8 且树中有一个值为 4 的节点，不能拿这个 4 自己配自己）；但它并不禁止两个值相同的不同节点——虽然标准 BST 通常约定节点值互不相同，实现时也不应依赖这条假设去写「值相等就跳过」的逻辑。

约束里的算法信号有两层。第一层是「二叉搜索树」：中序遍历会得到一个升序序列，天然可以套双指针；同时也可以对任意一个值 x 用 $O(h)$ 的时间去树中查找 k - x。第二层是节点数的规模在万级、节点值与 k 都在 $10^4 \sim 10^5$ 量级，说明 $O(n)$ 或 $O(n \log n)$ 都能过，不必为常数因子纠结，但 $O(n^2)$ 的两两枚举在极端退化成链的树上会吃紧。

值得注意的是：BST 的有序性在这道题里不是必需的。题目本质就是在一堆数里找和为 k 的一对，把树换成任意二叉树、甚至换成数组，问题都成立。识别出这一点，才不会被「二叉搜索树」四个字带着去做多余的上下界剪枝。

边界：根为空返回 false；只有一个节点时无论如何都凑不出两个不同节点，返回 false；节点值可以为负，k 也可以为负，所以不能用 0 或负数当哨兵；k - node.val 的取值范围在 int 内安全，不会溢出。

解法：DFS + 哈希集合记录补数

核心思路

先看暴力：对每个节点 x，再完整遍历一遍整棵树找有没有值为 k - x 的另一个节点。时间 $O(n^2)$，在节点数上万且树退化成链时是 $10^8$ 量级的节点访问，不划算。瓶颈在于每个节点的「找补数」都从零开始重扫全树，前面已经看过的信息一次都没被复用。

稍微好一点的做法是利用 BST：对每个节点 x，从根出发用 $O(h)$ 的时间二分查找 k - x，总复杂度 $O(n h)$。但这引入了一个恼人的细节——查到的那个节点可能就是 x 自己，必须额外判断「找到的节点是不是同一个节点对象」，而不能只比值。逻辑变复杂了，收益却有限。

换个角度：把「找一对和为 k 的数」这个经典问题剥离出树的外壳，它就是 1. 两数之和的原型。两数之和的标准解法是一次遍历 + 补数哈希——遍历到 x 时，不去问「后面有没有 k - x」，而是问「前面有没有 k - x」。这样每个数只需被检查一次，且天然保证配对的两个数来自不同位置。

于是得到本解法的不变量：在处理任意节点 node 的那一刻，集合 seen 中恰好装着按 DFS 前序顺序在 node 之前被访问过的所有节点的值，且这些节点与 node 一定是不同的节点。基于这个不变量，只要 seen.contains(k - node.val) 成立，就找到了一对合法的解；反之，若整棵树遍历完都没有命中，说明任意一对节点都不满足——因为任何一对节点在 DFS 序中总有先后，后被访问的那个必然会在自己被处理时于 seen 里看到先被访问的那个。

这里遍历顺序采用什么并不重要（前序、中序、后序、BFS 都行），因为不变量只要求「先访问的已入集合、当前的尚未入集合」。关键是先查再存：必须在把 node.val 放进集合之前完成查询，否则当 k 恰好等于 2 * node.val 时，节点会查到刚被自己塞进去的值，把自己和自己配成一对，违反「两个不同节点」的约束。

最后，返回值用 dfs(left) || dfs(right) 的短路或来串联：一旦左子树给出 true，右子树根本不会被访问，实现了「找到即停」。

解题步骤

在入口创建一个空的 HashSet<Integer> seen，把它作为参数贯穿整个递归。为什么要在入口建而不是在递归里建：这个集合必须被所有节点共享，代表「全局已访问过的值」；若在递归函数内部新建，每层都拿到空集合，等于什么都没记。

递归函数首先判空返回 false。为什么返回 false 而不是 true：false 是「这条分支没找到」的中性元，与上层的 || 组合时不会污染结果；空子树也确实不可能提供答案。

算出 need = k - node.val，先在 seen 中查询它。为什么必须先查后存：见核心思路中的说明，先存会让 k = 2 * node.val 的节点自己匹配自己。这是本题唯一的语义陷阱。

命中则立刻返回 true。为什么可以立刻返回：题目只要存在性，找到一对就足够，且 seen 里的值来自另一个节点，配对合法。

未命中则把 node.val 加入 seen。为什么加的是 node.val 而不是 need：集合的语义是「已经见过的值」，加 need 会把一个可能根本不存在的值当成已见过，导致后续节点误判为 true。

递归左右子树并用 || 连接返回。为什么用 || 而不是先算两边再取或：|| 在 Java 与 Go 中都是短路运算符，左子树返回 true 时右子树整棵都不会被遍历，这就是「找到即停」的实现方式。

以 具体用例 root = [5,3,6,2,4,null,7], k = 9 走一遍。这棵树的结构是：根 5，左孩子 3（其左右孩子为 2 和 4），右孩子 6（左孩子为空，右孩子为 7）。预期答案是 true，因为 2 + 7 = 9。

初始 seen = {}。DFS 按前序访问。
访问 5：need = 9 - 5 = 4，seen 为空不含 4，把 5 存入，seen = {5}。递归左子树。
访问 3：need = 9 - 3 = 6，seen = {5} 不含 6（注意树里其实有 6，但它在前序中排在 3 之后，此刻还没被访问，这正是不变量的体现——不用担心漏掉，等轮到 6 时它会反过来查到 3）。把 3 存入，seen = {5, 3}。递归左子树。
访问 2：need = 9 - 2 = 7，seen = {5, 3} 不含 7。存入，seen = {5, 3, 2}。左右孩子均为空，两次递归都返回 false。
回到 3 的右子树，访问 4：need = 9 - 4 = 5，seen 中含有 5，命中，返回 true。
这个 true 沿 dfs(3.left) || dfs(3.right) 向上传递，3 返回 true；再沿 dfs(5.left) || dfs(5.right) 传递，由于左侧已为 true，短路生效，节点 6 与 7 整棵右子树完全没有被访问，函数直接返回 true。

顺带看一个反例走查 root = [2,1,3], k = 4（预期 true，因为 1 + 3 = 4）：访问 2 时 need = 2，seen 为空未命中——注意此处若写成「先存后查」，seen 会先变成 {2}，紧接着查 need = 2 立刻命中，错误地把节点 2 与它自己配成一对返回 true（虽然本例最终答案碰巧也是 true，但把 k 换成 4 而树只有单节点 [2] 时，先存后查会返回 true，而正确答案是 false）。继续正确流程：存入 2，访问 1，need = 3 未命中，存入 1；访问 3，need = 1，seen = {2, 1} 命中，返回 true。

代码实现

class Solution {
    // 只要在遍历过程中记录出现过的值，当前值 x 只需判断 k - x 是否见过即可。
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> seen = new HashSet<>();
        return dfs(root, k, seen);
    }

    private boolean dfs(TreeNode node, int k, HashSet<Integer> seen) {
        if (node == null) {
            return false;
        }
        int need = k - node.val;
        if (seen.contains(need)) {
            return true;
        }
        seen.add(node.val);
        return dfs(node.left, k, seen) || dfs(node.right, k, seen);
    }
}

func findTarget(root *TreeNode, k int) bool {
    // 只要在遍历过程中记录出现过的值，当前值 x 只需判断 k - x 是否见过即可。
    seen := make(map[int]struct{})
    return dfs653(root, k, seen)
}

func dfs653(node *TreeNode, k int, seen map[int]struct{}) bool {
    if node == nil {
        return false
    }
    if _, ok := seen[k-node.Val]; ok {
        return true
    }
    seen[node.Val] = struct{}{}
    return dfs653(node.Left, k, seen) || dfs653(node.Right, k, seen)
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每个节点至多被访问一次，访问时只做一次减法、一次哈希查询和一次哈希插入，均摊都是常数；短路返回只会让实际访问的节点更少，不会更多。

空间复杂度：$O(n)$。凭什么：seen 最坏情况下要装下全部 $n$ 个节点值（当树中不存在任何满足条件的数对时），再加上递归调用栈的深度 $O(h)$；树退化成链时 $h = n$，两项都是 $O(n)$。这里不是 $O(1)$——哈希集合是这个解法的核心代价，也是它换取 $O(n)$ 时间所付的价钱。

关键点总结

先识别问题的骨架，再考虑容器的外壳。这道题贴着「二叉搜索树」的标签，但内核就是两数之和；把树看成一个「能被遍历一次的数的集合」之后，解法立刻明朗。遇到包装过的题目，先问「去掉数据结构的外衣，它到底在问什么」。

「先查后存」是补数哈希的铁律。查询发生在插入之前，才能保证配对的两个元素来自不同位置，这条规则在两数之和、和为 K 的子数组、四数相加等一整类题里完全通用。

不变量要能一句话说清「集合里此刻装的是什么」。这里是「DFS 序中排在当前节点之前的所有节点值」，有了这句话，正确性论证只剩一步：任意一对节点在 DFS 序里总有先后，后者必然能看见前者。

短路运算符是搜索类题目免费的剪枝。dfs(left) || dfs(right) 比先求两个布尔值再取或省下的可能是半棵树，写法上却毫无额外成本。

不要用值相等去判断「是不是同一个节点」。BST 通常保证值互不相同，但一旦题目允许重复值，靠值判同就会误判；靠遍历顺序（先查后存）来保证不同，才是与数据无关的稳健写法。

面试视角：这题的标准追问是「能不能不用额外的哈希集合」。答案是可以——利用 BST 中序有序的性质，用两个 173. 二叉搜索树迭代器式的栈分别做正序和逆序迭代，模拟 167. 两数之和 II 的对撞双指针，空间可降到 $O(h)$。主动说出「哈希法 $O(n)$ 空间但与树的形态无关，双指针法 $O(h)$ 空间但依赖 BST 有序性」这组权衡，比只写出一种解法更能拿分。

易错点总结

错误写法：先 seen.add(node.val) 再 seen.contains(k - node.val) → 用例 root = [1], k = 2，节点 1 把自己存进集合后立刻查到 2 - 1 = 1，返回 true；正确答案是 false，因为只有一个节点，凑不出两个不同的节点。

错误写法：在递归函数内部 HashSet<Integer> seen = new HashSet<>() → 用例 root = [5,3,6,2,4,null,7], k = 9，每层递归都拿到一个空集合，任何节点都看不到其他节点的值，恒返回 false。

错误写法：seen.add(need) 而不是 seen.add(node.val) → 用例 root = [2,1,3], k = 100，访问 2 时把 98 存进集合，访问 1 时 need = 99 未命中但把 99 存入，访问 3 时 need = 97 未命中；虽然本例结果碰巧对，但换成 root = [2,1,3], k = 5 时访问 2 存入 3、访问 1 时 need = 4 未命中存入 4、访问 3 时 need = 2 未命中，最终返回 false，而正确答案是 true（2 + 3 = 5）。

错误写法：return dfs(node.left, ...) | dfs(node.right, ...)（用按位或代替逻辑或） → 逻辑结果正确但失去短路，用例是一棵十万节点的链且答案在最左侧时，右子树仍被完整遍历，白白多花一倍时间。

错误写法：空节点返回 true → 用例 root = [1], k = 100，节点 1 的左右孩子都是空，各自返回 true，结果直接短路成 true；正确答案是 false。递归基的返回值必须是「未找到」这一侧的中性元。

错误写法：以为 BST 有序就写成「当前值大于 k 时剪枝不再往右走」 → 用例 root = [-5,-10,-1], k = -6，节点值允许为负，node.val > k 时右子树里仍可能有能与负数配成 k 的值，剪枝会漏解返回 false（正确答案是 true，-5 + -1 = -6）。

错误写法：把结果收集成中序数组后用 for i, for j 两层枚举 → 用例是一棵一万节点的树时约 $5 \times 10^7$ 次比较，虽然勉强能过但完全没用上有序性，且面试中会被直接判定为没有识别出两数之和的模板。

错误写法：中序遍历成数组后用双指针，却在 left == right 时仍然判定成立 → 用例 root = [3], k = 6，双指针初始 left = right = 0，nums[0] + nums[0] = 6 命中返回 true；对撞双指针的循环条件必须是 left < right，严格排除同一个元素。

错误写法：Go 中用 map[int]bool 却写成 if seen[k-node.Val] { ... } 并在别处误写 seen[x] = false → 一旦某个值被显式置为 false，它虽然存在于 map 中但判定为未见过，造成漏解；用 map[int]struct{} 加逗号 ok 判定可以从类型上杜绝这类失误。

相似题目

题目	难度	考察点
1. 两数之和	简单	本题的原型，容器是数组且要求返回下标，哈希表存的是「值 → 下标」的映射
167. 两数之和 II - 输入有序数组	中等	输入已有序，改用对撞双指针做到 $O(1)$ 额外空间，是本题 $O(h)$ 解法的原理来源
170. 两数之和 III - 数据结构设计	简单	变成在线设计题，要在插入与查询两个操作之间权衡把代价放在哪一侧
LCR 056. 两数之和 IV - 输入二叉搜索树	简单	与本题同题，可直接套用同一份代码
173. 二叉搜索树迭代器	中等	用栈把中序遍历拆成可暂停的迭代器，是把本题空间压到 $O(h)$ 的关键组件
230. 二叉搜索树中第 K 小的元素	中等	真正依赖中序有序性，靠计数提前终止，与本题「有序性可有可无」形成对照
98. 验证二叉搜索树	中等	依赖的是上下界约束而非中序序列，代表 BST 题的另一条主线
501. 二叉搜索树中的众数	简单	利用中序序列里相等元素必然相邻的性质做流式统计，考的是遍历中维护状态