1.题目描述
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
示例 1：
输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12
示例 2：
输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点
2.解题思路与代码
2.1 解题思路
非常简单的一道题目，首先遍历二叉树，然后将遍历的结果放入一个 HashSet 中，此时我们就得到了这棵二叉树的所有节点值。然后我们遍历这个 HashSet 中的元素，先用目标总和减去遍历到的节点值得到要查找的值 find，然后在这个 HashSet 中查找 find 是否存在，如果存在直接返回 true，表示有两个节点的值总和为目标 k，如果不存在继续便利。
这里需要注意如果当前节点的值与要查找的目标值相同，那么需要跳过这种情况，因为题目要求二叉树中节点的值是唯一的，因此虽然 HashSet 中包含 find，但此时找到的值就是当前节点，不满足题意。当然我们也可以使用 List 来存放二叉树节点的遍历结果。
2.2 代码
class Solution {
Set<Integer> set = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
process(root);
for (Integer key : set) {
int find = k - key;
if (find == key) {
continue;
}
if (set.contains(find)) {
return true;
}
}
return false;
}
public void process(TreeNode root) {
if (root == null) {
return;
}
process(root.left);
set.add(root.val);
process(root.right);
}
}
2.3 测试结果
通过测试
测试结果
3.总结
- 遍历二叉树，并将结果放入 HashSet 中
- 需要跳过查找值和节点值相同的情况
