树的后续遍历序列，BST

题目链接-来源：力扣（LeetCode）

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

 5
/ \

2 6
/
1 3
示例 1：

输入: [1,6,3,2,5]
输出: false

思路：

二叉搜索树（BST）的特征是，中序序列一定是按从小到大顺序排列的。也就是说，对于由相同元素组成的二叉树，其中序序列是唯一确定的（当然我们不一定非要用某种方法-比如排序-来确定中序序列，只需要知道它是唯一的即可）。
那么题目就简化成，知道中序序列，知道后序序列，我们可以唯一确定一棵二叉树，并判断其是否是BST。
我们考虑后序序列的特点，「左、右、根」，当前子树的根节点一定位于当前子序列（即排除了父节点的剩余序列）的最后。而BST的特点是，根节点左子树的元素都小于根节点元素，右子树元素都大于根节点元素。
综合以上两点，我们可以通过后序序列递归地确定一棵树的形状：

  • 从尾部确定根节点
  • 从后向前对剩余序列划分左右子树，先出现的较大元素优先考虑为右子树元素（否则右子树为空），剩余的较小元素划分为左子树元素。如果继续往前又出现了较大元素，则此树结构并非BST， 返回 false。
  • 对每个子树重复第一步，直到每个叶节点为止。
    若成功结束，则返回 true 。
    细节上，注意可能出现某侧子树为空的情况，划分子树的下标指针注意不要越界。
    时间复杂度：O(n²)
    空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verifyHelper(postorder, 0, postorder.length - 1);
    }
    
    private boolean verifyHelper(int[] arr, int start, int rootIndex) {
        if (start >= rootIndex) {
            return true;
        }
        int root = arr[rootIndex];
        int i = rootIndex - 1;
        while (i >= start && root < arr[i]) {
            i--;
        }
        int right = i + 1;
        while (i >= start && root > arr[i]) {
            i--;
        }
        if (i != start - 1) {
            return false;
        }
        boolean ret = true;
        if (right - 1 > start) {
            ret = ret && verifyHelper(arr, start, right - 1);
        } 
        if (right < rootIndex) {
            ret = ret && verifyHelper(arr, right, rootIndex - 1);
        }
        return ret;
        
    }
}