剑指 Offer 33. 二叉搜索树的后序遍历序列 (opens new window)

1.递归

分析：先从树的本身定义与后序遍历出发，划分根节点、左子树、右子树，根节点一定在子数组的右边界。然后再分别遍历左子树和右子树，与根节点比较，判断是否符合二叉搜索树定义。

具体来说，找到根节点后，左边子节点存在以下几种情况：

• 根节点左边第一个元素小于根节点，说明右子树为空。只要中间左子树有一个节点大于根节点返回false。
• 根节点左边第一个元素大于根节点，根节点左侧相邻大于根节点的最大连续子数组为右子树。剩余左侧部分为左子树。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length==0) return true;
        return dfs(postorder,0,postorder.length-1);
    }
    public boolean dfs(int[] postorder,int start,int end){
        if(start==end) return true;
        int root=postorder[end],right=-1;
        int mid=-1;
        if(postorder[end-1]>root){
            //找到右子树，并判断左子树合法性
            for(int i=end-1;i>=start;i--){
                if(postorder[i]<root){
                    mid=i;
                    for(int j=i-1;j>=start;j--){
                        if(postorder[j]>root) return false;
                    }
                    break;
                }
            }
            if(mid==-1){
                return dfs(postorder,start,end-1);
            }
            return dfs(postorder,start,mid)&&dfs(postorder,mid+1,end-1);
        }
        else{
            for(int i=end-1;i>=start;i--){
                if(postorder[i]>root) return false;
            }
            return dfs(postorder,start,end-1);
        }
        
    }
}