653. 两数之和 IV - 输入二叉搜索树
题目描述
输入一棵二叉搜索树的根节点 root（用层序数组表示）和一个整数 k。
判断树中能否找到两个不同的节点，使它们的值相加正好等于 k。能找到返回 true，否则返回 false。
示例 1
输入：root = [5,3,6,2,4,null,7], k = 9 输出：true
解释：例如 3 + 6 = 9，或 2 + 7 = 9。
示例 2
输入：root = [5,3,6,2,4,null,7], k = 28 输出：false
解释：树中任意两值之和都达不到 28。
数据范围
- 节点数在
[1, 10^4]范围内。 -10^4 <= Node.val <= 10^4- 保证
root是一棵合法的二叉搜索树。 -10^5 <= k <= 10^5
解题思路：深度优先搜索 + 哈希集合
和「两数之和」一样用哈希集合：遍历树的每个节点，先查 k - node.val 是否已在集合中，在就找到一对；不在就把 node.val 放进集合，继续遍历左右子树。先查后放保证不会把同一个节点用两次。（也可以利用 BST 中序有序，对中序数组用双指针。）
为什么正确
访问一个节点时，seen 中恰好是先于它被访问的全部节点值；若存在一对答案，当后访问的那个节点被检查时一定能发现。
复杂度分析
时间 O(n)，每个节点最多访问一次，哈希查询 O(1)；空间 O(n)。
易错点
要先查再放：如果先把 node.val 放进集合再查，k = 2·node.val 时会把同一个节点配对两次（例如 root=[1]，k=2 应返回 false）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
seen = set()
def dfs(node):
if not node:
return False
if k - node.val in seen:
return True
seen.add(node.val)
return dfs(node.left) or dfs(node.right)
return dfs(root)class Solution {
Set<Integer> seen = new HashSet<>();
boolean dfs(TreeNode node, int k) {
if (node == null)
return false;
if (seen.contains(k - node.val))
return true;
seen.add(node.val);
return dfs(node.left, k) || dfs(node.right, k);
}
public boolean findTarget(TreeNode root, int k) {
return dfs(root, k);
}
}class Solution {
unordered_set<int> seen;
bool dfs(TreeNode* node, int k) {
if (!node)
return false;
if (seen.count(k - node->val))
return true;
seen.insert(node->val);
return dfs(node->left, k) || dfs(node->right, k);
}
public:
bool findTarget(TreeNode* root, int k) {
return dfs(root, k);
}
};func findTarget(root *TreeNode, k int) bool {
seen := map[int]bool{}
var dfs func(node *TreeNode) bool
dfs = func(node *TreeNode) bool {
if node == nil {
return false
}
if seen[k-node.Val] {
return true
}
seen[node.Val] = true
return dfs(node.Left) || dfs(node.Right)
}
return dfs(root)
}var findTarget = function(root, k) {
const seen = new Set();
const dfs = (node) => {
if (!node)
return false;
if (seen.has(k - node.val))
return true;
seen.add(node.val);
return dfs(node.left) || dfs(node.right);
};
return dfs(root);
};function findTarget(root: TreeNode | null, k: number): boolean {
const seen = new Set<number>();
const dfs = (node: TreeNode | null): boolean => {
if (!node)
return false;
if (seen.has(k - node.val))
return true;
seen.add(node.val);
return dfs(node.left) || dfs(node.right);
};
return dfs(root);
}其他解法
哈希集合解法对任意二叉树都成立；中序遍历 + 双指针专门利用二叉搜索树有序，把问题归结为有序数组上的两数之和。
解法 2：中序遍历 + 双指针 时间 O(n)，空间 O(n)
二叉搜索树的中序遍历是升序序列。先中序遍历得到有序数组，再用左右双指针找和为 k 的两个数。和小于 k 就右移左指针，大于 k 就左移右指针。
用上了二叉搜索树的有序性，不需要哈希。代价是必须先完整遍历一遍，不能像哈希集合那样找到就提前结束。
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
vals = []
def inorder(node):
if not node:
return
inorder(node.left)
vals.append(node.val)
inorder(node.right)
inorder(root)
i, j = 0, len(vals) - 1
while i < j:
s = vals[i] + vals[j]
if s == k:
return True
if s < k:
i += 1
else:
j -= 1
return Falseclass Solution {
List<Integer> vals = new ArrayList<>();
void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
vals.add(node.val);
inorder(node.right);
}
public boolean findTarget(TreeNode root, int k) {
inorder(root);
int i = 0, j = vals.size() - 1;
while (i < j) {
int s = vals.get(i) + vals.get(j);
if (s == k) return true;
if (s < k) i++;
else j--;
}
return false;
}
}class Solution {
vector<int> vals;
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
vals.push_back(node->val);
inorder(node->right);
}
public:
bool findTarget(TreeNode* root, int k) {
inorder(root);
int i = 0, j = (int)vals.size() - 1;
while (i < j) {
int s = vals[i] + vals[j];
if (s == k) return true;
if (s < k) i++;
else j--;
}
return false;
}
};func findTarget(root *TreeNode, k int) bool {
vals := []int{}
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
vals = append(vals, node.Val)
inorder(node.Right)
}
inorder(root)
i, j := 0, len(vals)-1
for i < j {
s := vals[i] + vals[j]
if s == k {
return true
}
if s < k {
i++
} else {
j--
}
}
return false
}var findTarget = function(root, k) {
const vals = [];
const inorder = (node) => {
if (!node) return;
inorder(node.left);
vals.push(node.val);
inorder(node.right);
};
inorder(root);
let i = 0, j = vals.length - 1;
while (i < j) {
const s = vals[i] + vals[j];
if (s === k) return true;
if (s < k) i++;
else j--;
}
return false;
};function findTarget(root: TreeNode | null, k: number): boolean {
const vals: number[] = [];
const inorder = (node: TreeNode | null): void => {
if (!node) return;
inorder(node.left);
vals.push(node.val);
inorder(node.right);
};
inorder(root);
let i = 0, j = vals.length - 1;
while (i < j) {
const s = vals[i] + vals[j];
if (s === k) return true;
if (s < k) i++;
else j--;
}
return false;
}