二叉搜索树的后续遍历

【原题】 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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开发者杂谈

算法之逆序对

算法之逆序对 逆序对问题 ​ 假设A[1..n]是一个有n个不同数的数组。若iA[j],则对偶(i, j)称为A的一个逆序对(inversion)。 列出数组{...

3439
来自专栏zingpLiu

LeetCode【第1题】Two Sum

762
来自专栏Bingo的深度学习杂货店

Q125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric c...

3115
来自专栏Jack-Cui

541.Reverse String II(String-Easy)

Given a string and an integer k, you need to reverse the first k characters for ...

17410
来自专栏杨熹的专栏

【LEETCODE】模拟面试-39. Combination Sum

和subset区别:规定了子集的sum==target 注意,这里传递的起始位置是i,而不是position+1,but why??? helper(res, ...

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

洛谷P2312 解方程(暴力)

对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

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

HDU6315 Naive Operations(线段树 复杂度分析)

设\(d_i\)表示\(i\)号节点还需要加\(d_i\)次才能产生\(1\)的贡献

624
来自专栏desperate633

LintCode 插入区间题目分析代码

给出一个无重叠的按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你要确保列表中的区间仍然有序且不重叠 (如果有必要的话,可以合并区间)。

754
来自专栏King_3的技术专栏

leetcode-645-Set Mismatch

19311
来自专栏数据处理

leetcode222求完全二叉树节点个数

3054

扫码关注云+社区