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

import java.util.*;
public class Solution {
    // 二叉搜索树的后序遍历序列，判断某数组是否为某二叉搜索树的后序遍历
    // 二叉搜索树特性：左子树的所有节点都小于根节点，右子树所有节点都大于根节点；中序遍历是有序的
    // 后序遍历：左右根
    // 数组中最后的节点一定是根节点
    // 思路：根据最后一个节点时根节点，划分出左子树和右子树，左子树全部小于根节点，右子树全部大于根节点。划分完了之后，因为我们是根据第一个大于根节点的元素进行划分的，所以只需要验证划分出来的右子树全部大于根节点。之后递归进行这一过程
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 因为这里有一个递归出口了，但是真正的递归出口应该是sequence.length<1，所以将递归部分单独分开作为一个函数来写
        if (sequence.length == 0) return false;
        

        return Judge(sequence);
    }
    public boolean Judge(int[] sequence) {
        if (sequence.length < 1) return true;
        int i = 0;
        int root = sequence[sequence.length - 1];

        for (; i < sequence.length-1; i++) {
            // 找到根节点
            // 找到划分左右子树的点 i
            if (sequence[i] > root) {
                for (int j = i + 1; j < sequence.length - 1; j++) {
                    if (sequence[j] < root) {
                        return false;
                    }
                }
            }
        }
        // 递归遍历左子树
        boolean left = Judge(Arrays.copyOfRange(sequence, 0, i));
        // 递归遍历右子树
        boolean right = Judge(Arrays.copyOfRange(sequence, i, sequence.length - 1));

        return left && right;
    }
}