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.
Consider the following binary search tree:
5
/ \
2 6
/ \
1 3
Example 1:
Input: [5,2,6,1,3]
Output: false
Example 2:
Input: [5,2,1,3,6]
Output: true
Follow up: Could you do it using only constant space complexity?
2. Implementation
(1) Method 1
思路: preorder 是一个先递减再递增的顺序,维护一个单调递减栈,当前num如果大于栈顶数时,则更新min,如果当前num小于min则该序列并不是preorder序列
class Solution {
public boolean verifyPreorder(int[] preorder) {
Stack<Integer> stack = new Stack();
int min = Integer.MIN_VALUE;
for (int num : preorder) {
if (num < min) {
return false;
}
while (!stack.isEmpty() && stack.peek() < num) {
min = stack.pop();
}
stack.push(num);
}
return true;
}
}
3. Time & Space Complexity
Method 1: 时间复杂度 O(n), 空间复杂度O(n)
Last updated
Was this helpful?