Java——二叉搜索树的后序遍历序列

题目链接

牛客在线oj题——二叉搜索树的后序遍历序列

题目描述

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

数据范围：节点数量 0≤n≤1000 ，
节点上的值满足1≤val≤10^5 ，保证节点上的值各不相同
要求：空间复杂度 O(n) ，时间时间复杂度 O(n^2 )

提示：

二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
该题我们约定空树不是二叉搜索树
后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
参考下面的二叉搜索树，示例 1

题目示例

示例1

输入：
[1,3,2]

返回值：
true

说明：
是上图的后序遍历，返回true

示例2

输入：
[3,1,2]

返回值：
false

说明：
不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false

示例3

输入：
[5,7,6,9,11,10,8]

返回值：
true

解题思路

二叉搜索树的特点是父亲节点大于左子树所有节点的值，小于右子树所有节点的值

而后序遍历则是先遍历左子树，再遍历右子树，然后输出父节点的值

定义数组的第一个元素下标为start，最后一个元素下标为end。
首先拿到数组中最后一个节点end下标对应的的值，这个值就是父节点的值，然后从左到右遍历数组，当遇到比父节点的值更大的元素停止，这个节点下标为i
可以确定[start, i - 1]为当前遍历序列的左子树序列，而[i, end - 1]则是当前遍历序列的右子树序列

继续遍历[i, end - 1]序列，如果有元素小于父节点的值，说明这个序列不满足二叉搜索树的性质，返回false

需要注意的是，当前只是确定了当前序列是否满足二叉搜索树的性质，而我们需要判断所有的子树是否都满足二叉搜索树的性质，也就是说上述过程我们分别要对[start, i - 1]序列和[i, end - 1]序列分别再次验证

因此，可以通过递归来验证，最后的终止条件是：当start <= end时，返回true

完整代码

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

        int start = 0;
        int end = sequence.length - 1;
        return VerifySquenceOfBSTHelper(sequence, start, end);
    }

    private boolean VerifySquenceOfBSTHelper(int[] sequence, int start, int end) {
        if(start >= end){
            return true;
        }
        
        int root = sequence[end];
        int i = start;
        while(i < end && sequence[i] < root){
            i++;
        }
        for(int j = i; j < end; j++){
            if(sequence[j] < root){
                return false;
            }
        }
        return VerifySquenceOfBSTHelper(sequence, start, i - 1) && VerifySquenceOfBSTHelper(sequence, i, end - 1);
    }
}