Can Two Sum IV - Input is a BST be solved without extra space?

Yes, using a controlled in-order traversal with two stacks or iterative two-pointer method, but it requires careful pointer management to avoid extra arrays.

What is the difference between using DFS with a Hash Set and two-pointer in-order for this problem?

DFS with Hash Set checks complements on the fly with O(n) time and O(n) space, while in-order two-pointer requires building a sorted list first, also O(n) space, but can be more intuitive for ordered data.

How do duplicates affect the solution?

Since the problem asks for two distinct nodes summing to k, duplicates can be part of a valid pair only if they are separate nodes; failing to distinguish nodes may give incorrect results.

Is this approach applicable to regular binary trees?

Yes, but you cannot rely on in-order traversal to produce a sorted list; complement tracking with a Hash Set is safer for generic binary trees.

What is the main pattern to recognize in Two Sum IV - Input is a BST?

The key pattern is binary-tree traversal combined with state tracking of previously seen node values to detect pairs summing to k efficiently.

#653

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

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

给定一个二叉搜索树 root 和一个目标结果 k ，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true 。示例 1：输入: root = [5,3,6,2,4,null,7], k = 9 输出: true 示例 2：输入: root = [5,3,6,2,4,null…

哈希表双指针树深度优先搜索广度优先搜索

题目描述

给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示:

二叉树的节点个数的范围是 [1, 10⁴].
-10⁴ <= Node.val <= 10⁴
题目数据保证，输入的 root 是一棵有效的二叉搜索树
-10⁵ <= k <= 10⁵

lightbulb

解题思路

方法一：哈希表 + DFS

DFS 遍历二叉搜索树，对于每个节点，判断 k - node.val 是否在哈希表中，如果在，则返回 true，否则将 node.val 加入哈希表中。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉搜索树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        def dfs(root):
            if root is None:
                return False
            if k - root.val in vis:
                return True
            vis.add(root.val)
            return dfs(root.left) or dfs(root.right)

        vis = set()
        return dfs(root)

speed

复杂度分析

指标	值
时间	complexity ranges from O(n) for single-pass DFS or in-order list creation. Space complexity is O(n) for the Hash Set or sorted list to track visited node values. Recursive stack depth may add O(h) space, where h is the tree height.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may ask about handling duplicates or repeated values in the BST.
question_mark
They could probe whether in-order traversal or DFS is preferred for space efficiency.
question_mark
Expect questions about trade-offs between Hash Set lookup and two-pointer in-order strategies.

warning

常见陷阱

外企场景

error
Failing to check for the complement before adding the current node value to the Hash Set.
error
Confusing BST property with binary tree: in-order sorting only works due to BST ordering.
error
Attempting two-pointer logic without converting the BST to a sorted list, leading to incorrect index references.

swap_horiz

进阶变体

外企场景

arrow_right_alt
BST contains negative values or zeros, testing complement detection logic.
arrow_right_alt
The tree is unbalanced or skewed, affecting recursion stack depth and traversal order.
arrow_right_alt
Return all unique pairs summing to k instead of a boolean result.

help

常见问题

外企场景

继续练习

#530 二叉搜索树的最小绝对差 #783 二叉搜索树节点最小距离 #449 序列化和反序列化二叉搜索树