【15】二叉搜索树后序遍历序列

好久没有写题了，之前看到这题是没什么思路，今天看了没一会儿就有思路了，哈哈。

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

我的思路

其实很简单的，搜索树后序，最后一个元素为根，前一部分比根小的元素为左子树，后一部分大的为右子树，递归下去保证不在两部分中发现大小不对的元素就可以了。

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        return sequence.length != 0 && isBST(0, sequence.length - 1, sequence);
    }

    private boolean isBST(int start, int end, int[] sequence) {
        if (end - start < 2) {
            return true;
        }
        int root = sequence[end];
        int i = end - 1;
        while (i >= start &&  sequence[i] > root) {
            i--;
        }
        for (int j = i - 1; j >= start; j--) {
            if (sequence[j] >= root) {
                return false;
            }
        }
        return isBST(start, i, sequence) && isBST(i + 1, end - 1, sequence);
    }

}

其他方法

看到评论区有一种迭代的方法，思路其实和上面差不多，但是他每次大循环只消除数组最末尾一个元素。把前面数组看作一个新后序搜索树，新部分最后一个元素作为新根，把原来根的左子树看作是新根的左子树，因为一定比根小。但是访问次数其实是增多了。

class Solution {
        public:
        bool VerifySquenceOfBST(vector<int> sequence) {
            int size = sequence.size();
            if(0==size)return false;

            int i = 0;
            while(--size)
            {
                while(sequence[i++]<sequence[size]);
                while(sequence[i++]>sequence[size]);

                if(i<size)return false;
                i=0;
            }
            return true;
        }
    };