二叉搜索树的后续遍历

【原题】 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

621
来自专栏Petrichor的专栏

leetcode: 100. Same Tree

821
来自专栏数据结构与算法

POJ3233Matrix Power Series(矩阵快速幂)

给出$n \times n$的矩阵$A$,求$\sum_{i = 1}^k A^i $,每个元素对$m$取模

624
来自专栏武培轩的专栏

Leetcode#104. Maximum Depth of Binary Tree(二叉树的最大深度)

902
来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

693
来自专栏前端说吧

JS-几大排序算法(更新中...)

3085
来自专栏算法修养

ZOJ 3204 Connect them

Connect them ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- You have...

2666
来自专栏武培轩的专栏

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

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

3065
来自专栏xingoo, 一个梦想做发明家的程序员

Kruskal算法

同样是求最小生成树,kruskal适合从边的角度出发,因此适合稀疏图。而prim算法从点的角度出发,适合稠密图。 时间复杂度为O(eloge)。因为外层循环了e...

1675
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

873

扫码关注云+社区