题解 | #二叉搜索树的后序遍历序列#

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return reverse(sequence);
    }

    public boolean reverse(int[] sequence){
        //base case
        if(sequence.length <= 1) return true;
        //找到根节点
        int root = sequence[sequence.length - 1];
        //找分界点
        int index = 0;
        while(index < sequence.length - 1){
            if(sequence[index] > root){
                break;
            }
            index++;
        }
        //此时，index左边（左子树）都小于根节点，右子树待校验
        //进行校验
        int tmp = index;
        while(tmp < sequence.length - 1){
            if(sequence[tmp] < root){
                return false;
            }
            tmp++;
        }
        //递归校验左子树
        boolean left = reverse(Arrays.copyOfRange(sequence,0,index));
        //递归校验右子树
         boolean right = reverse(Arrays.copyOfRange(sequence,index,sequence.length - 1));
        return left && right;
    }
}

思路：

1. 二叉搜索树，可以想到二叉搜索树的特征。左子树所有节点值<根节点<右子树所有节点值
2. 后序遍历，数组最后一位是根节点。
3. 根据1的性质找到数组的分界点，分界点左边代表左子树，右边代表右子树
4. 对左右子树分别进行递归验证