二叉搜索树的后续遍历

【原题】 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 【思路】 后续遍历那么最后一个是根结点,由二叉搜索树的特征可以知道,可以把最后一个结点作为划分结点,找第一个大于根结点的左边作为左子树,右边(包含此元素)作为右子树。判断左右子树里面的元素是否满足左<根<右的关系,再依次递归判断左右子树。

public class Solution {
    public boolean VerifySquenceOfBSTCore(int [] sequence, int start, int end){
        if(end-start<=1) return true;//当只有一个元素或者为空时,肯定满足条件
        int root=sequence[end-1];
        int splitIndex=start;
        for(;splitIndex<end-1;splitIndex++)
            if(sequence[splitIndex]>root)//找左右子树的划分点
                break;
        for(int i=splitIndex;i<end-1;i++)
            if(sequence[i]<root) //再找到划分点的情况下,若右子树还有元素小于根结点,说明不满足二叉搜索树的条件,返回false
                return false;
        boolean left=true;
//递归判断左右子树是不是二叉搜索树
        left=VerifySquenceOfBSTCore(sequence,start,splitIndex);
        boolean right=true;
        right=VerifySquenceOfBSTCore(sequence,splitIndex,end-1);
        return left&&right;
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length<=0) return false;
        return VerifySquenceOfBSTCore(sequence, 0,sequence.length);
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java系列博客

Iterator在ArrayList中的源码实现

1452
来自专栏Java Edge

二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

4699
来自专栏前端说吧

JS - 二叉树算法实现与遍历 (更新中...)

3158
来自专栏俞其荣的博客

HashSet内部原理解析Header源码解析Footer

2725
来自专栏Netkiller

Java·日期时间处理

本文节选自《Netkiller Architect 手札》 1.4.3. Date 1.4.3.1. SimpleDateFormat public stati...

3684
来自专栏用户画像

剑指offer 二叉搜索树的后序遍历序列

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

772
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

801
来自专栏Hongten

ArrayList, LinkedList, Vector - dudu:史上最详解

ArrayList, LinkedList, Vector - dudu:史上最详解

813
来自专栏nnngu

Java中ArrayList与LinkedList的区别

Java中ArrayList与LinkedList的区别 一般大家都知道ArrayList和LinkedList的区别:       1. ArrayList的...

3696
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1735

扫码关注云+社区