剑指offer-二叉搜索树的后序遍历序列

本文为剑指 offer 系列第二十五篇。
主要知识点为二叉搜索树，判断一个序列是否为二叉搜索树的后序遍历序列。

题目描述

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

解题思路

二叉搜索树的性质就是根节点的值要大于左子树所有节点的值，要小于右子树的所有节点的值，左右子树又同样都是二叉搜索树。
后序遍历的顺序是左子树，右子树，然后根节点。
从而我们就可以得出结论，对于一个二叉搜索树的后序遍历来说，一定包含三部分（当然可能存在左右子树为空的情况）。首先最后一个节点是根节点，根节点前面的数据分为两部分，一部分都会比根节点小，这些是原来二叉搜索树的左子树，一部分都会比根节点要大，这就是原来二叉搜索树的右子树。我们在判断的时候可以设定本子树在序列中的左右边界，然后从右边界开始往前找，找到第一个比根节点小的索引，那么这个索引之前到左边界之间的节点的值都应该比根节点的值要小，否则就不会满足二叉搜索树的条件，返回false即可。
然后左右子树的序列又可以以同样的方式来进行判断是否为二叉搜索树。
又可以用一个完美的递归来解决这个问题。

解题代码

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> seq) {
        if(seq.size() == 0) return false;
        return helper(seq,0,seq.size()-1);
    }
    bool helper(vector<int>& a, int l, int r){
        if(l>=r) return true;
        int i  = r;
        while(i>l && a[i-1] > a[r]) i--;
        for(int j = i-1; j>=l;j--) if(a[j] > a[r]) return false;
        return helper(a,l,i-1) &&helper(a,i, r-1);
    }
};

时间复杂度为O(n),空间复杂度为O(n)

以上，本题结束！