剑指offer—二叉搜索树后序遍历验证 解答

剑指offer—二叉搜索树后序遍历验证

题目描述

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

思路

我们知道后序遍历最后一个节点是根节点,在二叉搜索树中,数组中比根节点小的数都是左子树,比根节点大的都是右子树,我们可以利用递归拆分数组区间进行判断

步骤

  • 第一次递归,此时区间为0 - length-1,区间>0,说明可以继续递归(跳出递归条件1:如果区间长度<=1,则输出true)
  • 获取根节点s[length-1]
  • 迭代找到根节点在数组中应该划分的位置(左边的小,右边的大),用一个变量dis存储,初始值为数组左区间下标,每次迭代+1,直到找到划分位置
  • 对划分位置右边的数进行判断,只要存在小于等于根节点值就返回false,说明不是正确的后序遍历
  • 递归判断它的左右两个子区间是否满足后序遍历

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] s) {
        return s.length==0?false:afterOrder(s,0,s.length-1);
    }
    public boolean afterOrder(int []s,int pre,int after){
        if(pre>=after) return true;
        int root = s[after];
        int dis = pre;
        while(s[dis]<root&&s[dis+1]<root&&dis<after)
            dis++;
        for(int i=dis+1;i<after;i++){
            if(s[i]<root){
                return false;
            }
        }
        return afterOrder(s,pre,dis)&&afterOrder(s,dis+1,after-1);
    }
}