前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【二叉树打卡1】二叉搜索树的后序遍历序列

【二叉树打卡1】二叉搜索树的后序遍历序列

作者头像
帅地
发布2019-06-06 15:34:44
3830
发布2019-06-06 15:34:44
举报
文章被收录于专栏:苦逼的码农

【题目】

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

【难度】

解答

一般对于二叉树的题目大多数都可以使用递归来做的,这道题也是用递归来多,思路如下:

二叉搜索树的后序序列有个这样的特点:序列的最后一个值为二叉树的根 root ;二叉搜索树左子树值都比 root 小,右子树值都比 root 大。

所以我们可以这样:

1、确定找出 root;

2、遍历序列(除去root结点),找到第一个大于root的位置,则该位置左边为左子树,右边为右子树;

3、遍历右子树,若发现有小于root的值,则是不符合二叉树搜索树的规则的,则直接返回false;

4、分别判断左子树和右子树是否仍是二叉搜索树(即递归步骤1、2、3)。

代码如下:

代码语言:javascript
复制
    public static boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length < 1)
            return false;
        return judge(sequence, 0, sequence.length - 1);
    }

    private static boolean judge(int[] sequence, int left, int right) {
        // 只有一个节点,递归结束
        if(left >= right)
            return true;
        // 最右边的节点相当于根节点
        int t = sequence[right]; 
        // 用来记录序列中第一个比根节点大节点的下标
        int index = right;
        for (int i = left; i <= right - 1; i++) {
            // 找到根节点的右孩子
            if (sequence[i] > t) {
                index = i;
                i++;
                // 如果右子树中有比根节点还小的树的话,显然是不成立的。
                while (i <= right - 1) {
                    if(sequence[i] < t)
                        return false;
                    i++;
                }
            }
        }
        // 递归检查左右子树
        return judge(sequence, left, index - 1) && judge(sequence,index, right - 1);
    }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-03-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 帅地玩编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 【题目】
  • 【难度】
  • 解答
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档