剑指offer - 二叉搜索树的后序遍历序列(Java实现)

题目链接：https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&&tqId=11176&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

二叉搜索树
  若它的左子树不为空，则左子树上面的所有节点的值均小于它的根节点的值。
  若它的右子树不为空，则右子树上面的所有节点的值均小于它的根节点的值。
  它的左、右子树分别都是二叉树。

  思路：通过后续遍历的一个过程，首先我们知道数组的最后一个节点是当前树的根节点，然后数组中前面某一部分属于这棵树的左子树，剩下的部分是这棵树的右子树。左子树：所有的点都小于根节点的值；右子树：所有的点都大于根节点的值。现在我来用下面的图来使用数组确定一个二叉搜索树的过程：

  根据上述流程我们可以看出，我们可以找到大于根节点的第一个数，在这之前的属于其左子树，在这之后的属于其右子树，如果右子树上的点有小于根节点的，说明我们无法构成一颗二叉搜索树；如果没有则继续判断其左子树，和右子树是否符合二叉树搜索树的后续遍历，如果最终只剩下一个结点，则表明当前子树是二叉搜索树的后续遍历序列。

import java.util.*;

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;//输入为空的情况
        int n = sequence.length;
        if(n == 1) return true;
        int root = sequence[n - 1];
        int inx = -1;
        for(int i = 0; i < n; ++ i) {
            if(sequence[i] >= root) {
                inx = i;
                break;
            }
        }
        for(int i  = inx; i < n - 1; ++ i) {
            if(sequence[i] < root) return false;
        }
        boolean l = true, r = true;
        if(inx > 0) {
            l = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, inx));
        }
        if(inx < n - 1) {
            r = VerifySquenceOfBST(Arrays.copyOfRange(sequence, inx, n - 1));
        }
        return l && r;
    }
}