题目

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

 

参考以下这颗二叉搜索树：

     5
    / \
    2  6
   / \
   1  3

示例 1：

输入: [1,6,3,2,5] 输出: false 示例 2：

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

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof

解题思路

参考：题解

二叉树后序遍历的顺序是：左->右->根，所以数组最后一个元素是根节点。

二叉树搜索树的特性：
* 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
* 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
* 它的左、右子树也分别为二叉搜索树

1. 从数组第0个元素开始往后找到第一个比根节点大的元素，该元素记为分割节点
2. 从分割节点到根结点的元素都要比跟节点大
3. 左右子树都应该满足1和2，递归即可，当分割的子树只有一个时，返回true,递归终止

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder,0,postorder.length-1);
    }
    public boolean helper(int[] postorder,int start,int end){
        //递归终止
        if(start>=end) return true;
        int idx=start;

        while(postorder[idx]<postorder[end]){
            idx++;
        } 
         /* 记录分割点 */
        int midIdx=idx;
        while(postorder[idx]>postorder[end]){
            idx++;
        }
        //判断左右子树
        boolean left = helper(postorder,start,midIdx-1);
        boolean right= helper(postorder,midIdx,end-1);
        return idx==end && left && right; 

    }
}