判断数组是否是二叉搜索树的后序遍历.md

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下二叉搜索树

     5
    / \
   2   6
  / \
 1   3

输入：[1,3,2,6,5]
输出：true

分析：二叉树的题以递归的思想，分别检查左右子树。如果一个序列是有效的，那么序列被分为三段，分别是小于根节点的左子树，大于根结点的右子树，根节点。

    1   3   2       6          3
    |-  左  -|    |-右-｜   ｜-根结点-｜ 

如果有效，那么左子树中的节点必须都小于根结点，右子树的节点都大于根结点。

1. 先对树进行划分，树的范围为 [left,right]，分割成两个子树。根结点为right。
2. 分割条件为从左边界向右遍历，找到第一个大于根结点的下标mid，因此[left,mid-1]为左子树，[mid,right]为右子树。
3. 由于左子树中都可以确定均小于根结点，因此需要额外确认右子树中的节点是否都大于根结点。遍历[mid,right]检查是否满足条件。
4. 递归遍历左右孩子，当left>=right时说明此时子树只有一个节点，直接返回true。

C++代码

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return verifyPostorderHelper(postorder,0,postorder.size()-1);
    }
    bool verifyPostorderHelper(vector<int>& postorder,int start,int end){
        if(start>=end){
            return true;
        }
        int p = start;
        while(postorder[p] < postorder[end]) { p++;}
        int partirion = p;
        while(p<end){
            if(postorder[p]<postorder[end]) { return false; }
            p++;
        }
        return verifyPostorderHelper(postorder,start,partirion-1) && verifyPostorderHelper(postorder,partirion,end-1);
    }
};