Description
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?
Solution
DFS, time O(n * log n), space O(1)
这道题在递归到子问题之前，需要做剪枝，否则有些test case会TLE。
class Solution {
public boolean verifyPreorder(int[] preorder) {
return verify(preorder, 0, preorder.length - 1);
}
public boolean verify(int[] preorder, int start, int end) {
if (start > end) {
return true;
}
int pivot = preorder[start];
int rightStart = -1; // start index of right subtree
for (int i = start + 1; i <= end; ++i) {
if (rightStart == -1 && preorder[i] > pivot) {
rightStart = i;
} else if (rightStart != -1 && preorder[i] < pivot) {
return false; // prune!
}
}
return rightStart == -1
? verify(preorder, start + 1, end)
: verify(preorder, start + 1, rightStart - 1)
&& verify(preorder, rightStart, end);
}
}
Stack, time O(n), space O(n)
非常有趣的写法，值得深思...
class Solution {
public boolean verifyPreorder(int[] preorder) {
int min = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<>();
for (int val : preorder) {
if (val < min) {
return false;
}
while (!stack.empty() && stack.peek() < val) { // enters right subtree
min = stack.pop(); // pop nodes in the left of val and update min
}
stack.push(val);
}
return true;
}
}
