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?
Solution1：
4(min)
2 *6
1 3 5 7
[4 2 1 3 6 5 7]
思路： 模拟树遍历的过程。遍历输入数组，对当前元素elem，它的上限是没有问题的，可以就当作树中右侧新的branch。但需要check它的下限，不能小于它parent结点的值min_th。min_th通过stack维持。
Time Complexity: O(N) Space Complexity: O(N)
Solution2：在输入数组前部自身 当作stack：维持指针i
思路： 不会影响正常的遍历
Time Complexity: O(N) Space Complexity: O(1)
Solution1 Code：
class Solution {
public boolean verifyPreorder(int[] preorder) {
int min_th = Integer.MIN_VALUE;
Deque<Integer> stack = new ArrayDeque();
for (int elem : preorder) {
if (elem < min_th) return false;
while (!stack.isEmpty() && elem > stack.peek()) // right branch
min_th = stack.pop();
stack.push(elem);
}
return true;
}
}
Solution2 Code：
class Solution {
public boolean verifyPreorder(int[] preorder) {
int min_th = Integer.MIN_VALUE, i = -1;
for (int elem : preorder) {
if (elem < min_th) return false;
while (i >= 0 && elem > preorder[i])
min_th = preorder[i--];
preorder[++i] = elem;
}
return true;
}
}
