255. 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?

解法1：

吃透了bst的性质就好做了：
第一个数字是root，之后找出所有比他大的和所有比他小的范围。
对large 和small分别做递归。
要注意如果left > right return true
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return true;
        }   
        return helper(preorder, 0, preorder.length - 1);
    }
    private boolean helper(int[] preorder, int left, int right) {
        if (left > right) {
            return true;
        }
        if (left == right) {
            return true;
        }
        // root is the first one
        int root = preorder[left];
        // check [left, right] find first index that is larger than root
        int i = left + 1;
        for (;i <= right; i++) {
            if (preorder[i] > root) {
                break;
            }
        }
        if (i > right) {
            return helper(preorder, left + 1, right);
        }
        if (i == right) {
            return helper(preorder, left + 1, right - 1);   
        }
        // check if [i, right] has one element that is smaller than root
        for (int j = i; j <= right; j++) {
            if (preorder[j] < root) {
                return false;
            }
        }
        return helper(preorder, left + 1, i - 1) && helper(preorder, i, right);
    }
}

解法2： Stack O(N) Time + O(N) Space

基本的思想是，用一个stack来维护当前的树，如果一个数字比栈顶的数字小，那么就认为是当前数的左子树，而如果比栈顶的大，那么说明是其中一个node的右字树，那么就需要把栈顶弹出，同时需要更新当前的low，之后所有的点都必须要比这个low大，如果不符合这一点就不是BST。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int lower = Integer.MIN_VALUE;
        for (int i = 0; i < preorder.length; i++) {
            int p = preorder[i];
            if (p < lower) {
                return false;
            }
            while (!stack.isEmpty() && p > stack.peek()) {
                lower = stack.pop();
            }
            stack.push(p);
        }
        return true;
    }
}

解法3： Follow Up Stack O(N) Time + O(1) Space

为了节省空间，就直接用preorder这个数组来当成stack就可以了。

lang: java
1
2
3
4
5
6
7
8
9
10
11
public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE, i = -1;
    for (int p : preorder) {
        if (p < low)
            return false;
        while (i >= 0 && p > preorder[i])
            low = preorder[i--];
        preorder[++i] = p;
    }
    return true;
}