LeetCode 255. Verify Preorder Sequence in Binary Search Tree（检查二叉搜索树的前序遍历）

原题网址：https://leetcode.com/problems/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?

方法一：分治策略，根据二叉搜索树的特性，分别寻找匹配当前节点的左子树和右子树。需要使用递归。

public class Solution {
    private int range(int[] preorder, int from, int min, int max) {
        if (from == preorder.length) return from;
        if (preorder[from] < min || preorder[from] > max) return from;
        int small = range(preorder, from+1, min, preorder[from]-1);
        int great = range(preorder, small, preorder[from]+1, max);
        return great;
    }
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) return true;
        int small = range(preorder, 1, Integer.MIN_VALUE, preorder[0]-1);
        int great = range(preorder, small, preorder[0]+1, Integer.MAX_VALUE);
        return great == preorder.length;
    }
}
           

代码参考：http://my.oschina.net/u/922297/blog/498356

方法二：前序遍历的特点，是节点遍历先减后增，减的时候可以随意减少，但开始增加的时候，表明正在右子树，则往后的任何值都不能小于当前节点的值。

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack<>();
        int min = Integer.MIN_VALUE;
        for(int node: preorder) {
            if (node < min) return false;
            while (!stack.isEmpty() && stack.peek() < node) min = stack.pop();
            stack.push(node);
        }
        return true;
    }
}
           

如果允许我们修改来源数据的话，就可以使用preorder作为栈，而不需要额外分配空间：

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int size = 0;
        int min = Integer.MIN_VALUE;
        for(int node: preorder) {
            if (node < min) return false;
            while (size > 0 && preorder[size-1] < node) min = preorder[--size];
            preorder[size++] = node;
        }
        return true;
    }
}
           

但原理是一样的。

参考文章：https://segmentfault.com/a/1190000003874375