编程习题二叉搜索树的后序遍历序列求解,输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
使用递归的方式,交替进行处理
java
public class Solution { public boolean VerifySquenceOfBST(int[] arr) { if (arr == null || arr.length == 0) { return false; } return isBST(arr, 0, arr.length - 1); } private boolean isBST(int[] arr, int start, int end) { if (start >= end) { return true; } int root = arr[end]; int p1 = start; while (p1 < end && arr[p1] < root) { p1++; } int p2 = p1; while (p2 < end) { if (arr[p2] < root) { return false; } else { p2++; } } boolean left = isBST(arr, start, p1 - 1); boolean right = isBST(arr, p1, end - 1); return left && right; } }