推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

 

题目描述

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

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        
    }
}

 

思路：

先回顾了解一下二叉搜索树：

二叉搜索树（Binary Search Tree），（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
列如：

我们写一下上面这个二叉搜索树的后续遍历(左右根)：

2，5，3，8，7，6 

根据后续遍历规则以及二叉搜索树的规则，我们可以知道：

  1. 最后一个元素是根节点；
  2. 比最后一个元素大的，是树的右子树的元素；比最后一个树小的，是树的左子树的元素；

综上，我们可以将树划分成  [2，5，3]  [8，7]  [6]

其中 [6]是根结点，  [2，5，3] 是左子树的后续遍历， [8，7] 是右子树的后续遍历。

我们可以将划分出来的 左子树 和 右子树 再继续按照上述方法划分；

一直到将元素划分完，划分过程中，如果没有违反二叉搜索树的规则，就说明改后续遍历是某二叉搜索树的后续遍历。

 

实现：

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0)
            return false;
        return check(sequence,0,sequence.length - 1);
    }
    
    private boolean check(int[] sequence, int first, int last){
        if (last - first <= 1)
            return true;
        int rootVal = sequence[last];
        int cutIndex = first;
        while (cutIndex < last && sequence[cutIndex] <= rootVal)
            cutIndex++;
        for (int i = cutIndex; i < last; i ++)
            if (sequence[i] < rootVal)
                return false;
        return check(sequence,first,cutIndex - 1) && check(sequence,cutIndex,last -1);
    }
    
}

 

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！