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

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

    public boolean func(int[] sequence) {
        if (sequence == null || sequence.length == 0) return true;
        int t = sequence[sequence.length - 1];
        int left_idx = -1;
        int right_idx = -1;
        for (int i = 0; i < sequence.length - 2; i++) {
            if (sequence[i] > t) {
                right_idx = i;
                break;
            }
        }

        if (right_idx == -1) {
            return func(Arrays.copyOfRange(sequence, 0, sequence.length - 1));
        }

        for(int i=right_idx;i<sequence.length-1;i++){
            if(sequence[i]<t){
                return false;
            }
        }

        return func(Arrays.copyOfRange(sequence, 0, right_idx)) &&
               func(Arrays.copyOfRange(sequence, right_idx,
                                  sequence.length - 1));
    }
}

这个题目的解题思路如下：

考虑到二叉排序树的特点(左子树上面的全部节点值都比根节点小，右子树上面的全部节点值都比根节点大)，又考虑到后序排序的特点，根节点一定是数组中的最后一个节点。这样的话可以把数组分为左子树、右子树、根三个部分。那么先找到左右子树的分割点(也就是从前往后遍历数组第一个比根大的节点)，然后判断右子树中是否所有节点值都比根大，如果不是，说明这个数组不是后序遍历的结果。如果是，则递归遍历判断左右子树。