前言
剑指 Offer II 056. 二叉搜索树中两个节点之和
三种做法，和一个错误解法。
题目描述
![image-20220326205314543]()
1.层序遍历+哈希表
广度优先搜索实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean findTarget(TreeNode root, int k) {
Deque<TreeNode> q = new LinkedList<>();
Set<Integer> set = new HashSet<>();
q.add(root);
while (!q.isEmpty()) {
TreeNode cur = q.pop();
if (set.contains(k - cur.val)) {
return true;
}
set.add(cur.val);
if (cur.left != null) q.add(cur.left);
if (cur.right != null) q.add(cur.right);
}
return false;
}
}
|
2.前序遍历+哈希表
深度优先搜索实现
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
return dfs(root, set, k);
}
boolean dfs(TreeNode root, Set<Integer> set, int k) {
if (root == null) return false;
if (set.contains(k - root.val)) return true;
set.add(root.val);
return dfs(root.left, set, k) || dfs(root.right, set, k);
}
}
|
3.中序遍历+双指针
迭代实现中序遍历
根据BST的特点，中序遍历输出一定是单调递增的
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean findTarget(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
List<Integer> arr = new ArrayList<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pollFirst();
arr.add(cur.val);
cur = cur.right;
}
int left = 0, right = arr.size() - 1;
while (left < right) {
if (arr.get(left) + arr.get(right) == k) return true;
else if (arr.get(left) + arr.get(right) < k) left++;
else right--;
}
return false;
}
}
|
4.错误做法
如果目标节点不具备祖先-后代关系，此方法失效。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) return false;
return check(root.left, k - root.val) || check(root.right, k - root.val)
|| findTarget(root.left, k) || findTarget(root.right, k);
}
boolean check(TreeNode root, int val) {
if (root == null) return false;
if (root.val == val) return true;
if (val < root.val) return check(root.left, val);
else return check(root.right, val);
}
}
|
