LC255. Verify Preorder Sequence in Binary Search Tree
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?
此题给了preorder序列，判断这棵树是不是BST。
Preorder：根左右
Stack solution:
Since preorder, and left should be less than its root, so we can keep a stack of nodes when we are in left subtree, when the value gets larger, means we go to the right part, we pop all smaller items in stack, the last one is the new min value of current value in the array. When coming right, it means the value will always be larger. If all nums in array do not violate the rules, return true, otherwise return false.
利用栈存所有左侧的值，如果遇到当前array里的值大的话就pop所有小于它的值，最后一个pop的就是min。如果还在左边，就一直push值进栈，栈顶是最小值。
public boolean verifyPreorder(int[] preorder) {
int low = Integer.MIN_VALUE;
Stack<Integer> path = new Stack();
for (int p : preorder) {
if (p < low)
return false;
while (!path.empty() && p > path.peek())
low = path.pop();
path.push(p);
}
return true;
}
O(n), O(n)
Follow up:
Use pointers to array to replace the stack, pop means pointers go to previous index, push means pointers goto next and change the num in array.
利用指针来替代栈，当前指针标记栈顶所在。
public class Solution {
public boolean verifyPreorder(int[] preorder) {
// preorder - root, left, right
// so in the left side the value can be as small as it can be, in the right side it should be larger than before
int i = -1, min = Integer.MIN_VALUE;
for(int p: preorder){
if(p < min) return false;
while(i >= 0 && p > preorder[i]){
// pop peek of stack
min = preorder[i--];
}
// push p
preorder[++i] = p;
}
return true;
}
}
O(n), O(1)
Verify in-order array?
Inorder is a sequential array. Just check array[i] > array[i-1].
Verify post-order array?
Post-order: left - right - root
Use the same algorithm as pre-order, checking from the end of array to the start, and changing less than to larger than, each time we record the max value instead of the min value.
public boolean verifyPostorder(int[] postorder)
{
int i = postorder.length;
int max = Integer.MAX_VALUE;
for (int j = postorder.length - 1; j >= 0; j--)
{
if (postorder[j] > max) return false;
while (i < postorder.length && postorder[j] > postorder[i])
max = postorder[i++];
postorder[--i] = postorder[j];
}
return true;
}
O(n), O(1).