255 Verify Preorder Sequence in Binary Search Tree

1. Question

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?

2. Implementation

思路:前序遍历的规律是数组是先递减然后再递增,所以我们维护一个变量min和单调递减的stack,表示当前最小的数值,如果当前的数小于min则返回false。如果栈顶的数比当前的数小,则将min更新为栈顶的数。
1
public class Solution {
2
public boolean verifyPreorder(int[] preorder) {
3
int min = Integer.MIN_VALUE;
4
5
Stack<Integer> stack = new Stack<>();
6
7
for (int num : preorder) {
8
if (num < min) {
9
return false;
10
}
11
12
while (!stack.isEmpty() && stack.peek() < num) {
13
min = stack.pop();
14
}
15
stack.push(num);
16
}
17
return true;
18
}
19
}
Copied!
Follow up: 题目要求要constant space, 我们可以直接用原数组模拟stack
1
class Solution {
2
public boolean verifyPreorder(int[] preorder) {
3
int index = -1;
4
int min = Integer.MIN_VALUE;
5
6
for (int num : preorder) {
7
if (num < min) {
8
return false;
9
}
10
11
while (index >= 0 && preorder[index] < num) {
12
min = preorder[index--];
13
}
14
preorder[++index] = num;
15
}
16
return true;
17
}
18
}
Copied!

3. Time & Space Complexity

时间都是O(n),利用栈的话空间复杂度是O(n), follow-up的做法空间复杂度是O(1)