-
Notifications
You must be signed in to change notification settings - Fork 2
/
TwoSumBST.java
114 lines (102 loc) · 2.91 KB
/
TwoSumBST.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package Leetcode;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* @author kalpak
* Given the root of a Binary Search Tree and a target number k,
* return true if there exist two elements in the BST such that their sum is equal to the given target.
*
* Example 1:
* Input: root = [5,3,6,2,4,null,7], k = 9
* Output: true
*
* Example 2:
* Input: root = [5,3,6,2,4,null,7], k = 28
* Output: false
*
* Example 3:
* Input: root = [2,1,3], k = 4
* Output: true
*
* Example 4:
* Input: root = [2,1,3], k = 1
* Output: false
*
* Example 5:
* Input: root = [2,1,3], k = 3
* Output: true
*
* Constraints:
* The number of nodes in the tree is in the range [1, 104].
* -104 <= Node.val <= 104
* root is guaranteed to be a valid binary search tree.
* -105 <= k <= 105
*/
/**
* Time Complexity : O(n)
* Space Complexity : O(log n)
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class TwoSumBST {
public boolean findTarget(TreeNode root, int k) {
if(root == null)
return false;
// Use Deque as Stack
Deque<TreeNode> leftSide = new ArrayDeque<>();
Deque<TreeNode> rightSide = new ArrayDeque<>();
TreeNode temp = root;
while(temp != null) {
leftSide.push(temp);
temp = temp.left;
}
temp = root;
while(temp!= null) {
rightSide.push(temp);
temp = temp.right;
}
// Use 2 pointer style traversal.
// But traverse the tree to looking for the next smaller or larger TreeNode.
// This is applicable since this is a BST.
TreeNode leftNode = leftSide.pop();
TreeNode rightNode = rightSide.pop();
while (leftNode.val != rightNode.val) {
// left.val == right.val indicates a thorough search is completed.
int currSum = leftNode.val + rightNode.val;
if (currSum == k) {
return true;
} else if (currSum < k) {
if (leftNode.right != null) {
leftNode = leftNode.right;
while (leftNode != null) {
leftSide.push(leftNode);
leftNode = leftNode.left;
}
}
leftNode = leftSide.pop();
} else { // currSum > k
if (rightNode.left != null) {
rightNode = rightNode.left;
while (rightNode != null) {
rightSide.push(rightNode);
rightNode = rightNode.right;
}
}
rightNode = rightSide.pop();
}
}
return false;
}
}