-
Notifications
You must be signed in to change notification settings - Fork 59
/
Leetcode: Verify preorder sequence of Binary Search Tree
53 lines (39 loc) · 1.68 KB
/
Leetcode: Verify preorder sequence of Binary Search Tree
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
Leetcode: Verify preorder sequence of Binary Search Tree
Question
You have an array of preorder traversal of Binary Search Tree ( BST). Your program should verify whether it is a correct sequence or not.
Input: Array of Integer [ Pre-order BST ]
Output: String “Yes” or “No”
Solution 1
divide and conquer
bool verifyPreorder(vector<int>& preorder) {
int n = preorder.size();
return helper(preorder, 0, n-1, INT_MIN, INT_MAX);
}
bool helper(vector<int>& preorder, int s, int e, int lb, int ub){
if(s>=e) return true;
int r = preorder[s];
int i = s;
while(i<=e && preorder[i]<=r){
if(preorder[i]<lb || preorder[i]>ub) return false;
i++;
}
return helper(preorder, s+1, i-1, lb, r-1) &&
helper(preorder, i, e, r+1, ub);
}
Solution 2
simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN; // lower bound
stack<int> path;
for (int p : preorder) {
if (p < low) {
return false;
}
while (!path.empty() && p > path.top()) {
low = path.top();
path.pop();
}
path.push(p);
}
return true;
}