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.
一刷
题解：
具体的思路是，利用栈，实现preorder traversal。具体的措施是，压栈root, left, 如果是right，则弹出对应的left和root
Time complexity O(n), space complexity O(logn)
public class Solution {
public boolean verifyPreorder(int[] preorder) {
int low = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<>();
for(int i : preorder){
if(i<low) return false;
while(!stack.isEmpty() && i>stack.peek()) low = stack.pop();
stack.push(i);
}
return true;
}
}
不使用Stack，Space Complexity O(1)的解法， 利用了原数组
public class Solution {
public boolean verifyPreorder(int[] preorder) {
int low = Integer.MIN_VALUE, index = -1;
for(int i : preorder){
if(i<low) return false;
while(index>=0 && i>preorder[index]) low = preorder[index--];
preorder[++index] = i;
}
return true;
}
}
二刷
还是忘记了。不用递归，perorder, inorder, postorder都要用栈实现。
Stack
public class Solution {
public boolean verifyPreorder(int[] preorder) {
int low = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<>();
for(int i:preorder){
if(i<low) return false;
while(!stack.isEmpty() && i>stack.peek()) low = stack.pop();
stack.push(i);
}
return true;
}
}
