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

约 4 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 滑动窗口

题目描述

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

image-20260929010227885

题意分析

判断树中是否存在两个不同节点，使它们的值之和等于 k。只需返回是否存在，不能让同一个节点与自己配对。

遍历到值为 x 的节点时，需要寻找的另一个值就是 k - x。把已经访问的值保存起来，就能在遍历过程中完成配对。

解法：DFS 与已见值集合

核心思路

[!blue]

使用整次 DFS 共享的集合 nodes。访问当前节点之前，集合只包含此前访问过的节点值；先查询补数 k - root.val，命中就说明有一个先前的节点能与当前节点组成答案。

先查询、后插入保证两个节点不同。若先插入当前值，当目标恰好是它的两倍时，就可能错误地让当前节点使用两次。

查询没有命中，再将当前值加入集合，继续搜索左右子树。集合记录的是全树已经访问的值，不只是当前递归路径，所以回溯时不删除值，也不能在切换子树时清空。合法配对可能分处左右两棵子树。

如果确实存在一对节点，后访问的那个节点查询时，先访问的值一定还在集合中，所以不会漏掉答案。任一子树找到后就直接返回 true，短路或会停止剩余搜索；遍历完仍未命中才返回 false。

这个方法依赖的是遍历与补数查询，不要求使用二叉搜索树的大小关系。节点值和目标可以为负，不能只凭当前值超过目标就提前剪枝。

解题步骤

  1. 建立整次搜索共用的空集合，从根节点开始 DFS。
  2. 空节点返回 false；非空节点先查补数，存在则立即返回 true。
  3. 补数不存在时，将当前值插入集合，再搜索左、右子树。
  4. 两边任意一边找到就返回 true，全部搜索结束仍未找到则返回 false。单节点树会因为查表时集合为空而自然返回 false。

代码实现

class Solution {
    private Set<Integer> nodes;

    public boolean findTarget(TreeNode root, int k) {
        nodes = new HashSet<>();

        return find(root, k);
    }

    private boolean find(TreeNode root, int k) {
        if (root == null) {
            return false;
        }

        if (nodes.contains(k - root.val)) {
            return true;
        }

        nodes.add(root.val);

        return find(root.left, k) || find(root.right, k);
    }
}

func findTarget(root *TreeNode, k int) bool {
    nodes := make(map[int]bool)

    var find func(root *TreeNode, k int) bool
    find = func(root *TreeNode, k int) bool {
        if root == nil {
            return false
        }
        if nodes[k-root.Val] {
            return true
        }
        nodes[root.Val] = true
        return find(root.Left, k) || find(root.Right, k)
    }
    return find(root, k)
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，n 为节点数，每个节点至多做一次哈希查询和插入。
  • 空间复杂度：$O(n)$，集合最多保存所有节点值，递归栈另需 $O(h)$，其中树高 h 不超过 n。

关键点总结

[!green]

  • 配对转化为查询补数，后访问的节点负责识别这一对。
  • 查询发生在插入当前值之前，集合中的配对对象必然是另一个节点。
  • 已见集合跨子树共享，回溯时不撤销已访问值。

易错点总结

[!yellow]

  • 先插入再查询：可能把一个节点与自己配对。
  • 每棵子树单独建立集合：会漏掉分属不同子树的两个节点。
  • 返回父节点时删除已见值：集合会退化成当前路径，无法覆盖整个遍历历史。
  • 依据当前值大于目标就剪枝：另一半可能为负，这个条件不能排除配对。
  • 搜索到空节点返回 true：空子树不能提供配对，应返回 false。

相似题目

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