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

约 4 分钟
文章信息 7 个分类 7 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 阿里
标签
哈希表 深度优先搜索 树 广度优先搜索 二叉树 双指针 二叉搜索树

题目描述

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

image-20260928224412584

image-20260928224412586

题意分析

判断树中能否选出两个不同节点，使它们的值之和等于 k。遍历当前值 x 时，只需知道之前是否访问过值为 k - x 的另一个节点，可以用哈希集合保存这些已访问值。

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

核心思路

[!blue]

创建贯穿整次遍历的集合 seen。进入一个非空节点时，集合中只包含此前已经访问过的节点值；先查找补数 k - node.val，命中就说明找到了另一个节点，立即返回 true。

查询失败后，才把当前值加入集合，再递归左右子树。这个顺序保证当前节点不能与自己配对，即使目标刚好是当前值的两倍，也必须先找到另一个已访问节点。

任意一对合法节点在遍历中都有先后：先访问者会留在集合中，后访问者一定能查到它，因此不会漏解。集合在递归返回时不能删除旧值，因为一对节点也可能分别位于左右子树；这里保存的是整个已访问部分，而不只是当前递归路径。

左子树找到后通过逻辑或直接结束，否则继续搜索右子树。两边都未找到才返回 false。这个判据只依赖节点值与访问先后，二叉搜索树的有序性不影响它的正确性。

解题步骤

  1. 在入口创建空集合，并传给整次 DFS。
  2. 遇到空节点返回 false。
  3. 查询当前值的补数；命中返回 true，未命中则登记当前值。
  4. 依次搜索左右子树，用短路逻辑或合并结果。
  5. 若树中只有一个节点，它查询时集合为空，两棵子树也为空，最终返回 false。

代码实现

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)$。集合最多保存 $n$ 个值，递归栈深度为树高 $h$，两者合计 $O(n+h)=O(n)$。

关键点总结

[!green]

  • 先查后存，从顺序上保证不能与自己配对。
  • 集合贯穿整个遍历，不能每层重新创建。
  • 递归返回时保留已访问值，才能找到跨左右子树的配对。

易错点总结

[!yellow]

  • 当前值先入集合，目标为当前值两倍时会与自己配对。
  • 每个递归层重新建集合，会丢失之前访问的信息。
  • 空节点返回真，会把空分支当作找到答案。

相似题目

题目 难度 关联与区别
167. 两数之和 II - 输入有序数组 中等 BST中序有序，可把双指针的两端访问改为两个方向的迭代器，避免完整数组。
173. 二叉搜索树迭代器 中等 迭代器提供按序逐个取节点的子过程，两个方向可配合寻找目标和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/leetcode-653
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！