33:二叉搜索树的后序遍历序列

题目33:二叉搜索树的后序遍历序列

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

举例说明

输入数组{5,7,6,9,11,10,8},则返回true,因为这个整数序列是可以展开为一二叉搜索树的后序遍历结果。
如果输入的数组是{7,4,6,5},则由于没有哪棵二叉搜索树的后序遍历结果是这个序列,因此返回false。

思路

和二叉树有关的问题,很多都可以递归解决,因为子问题和本问题具有一致性。关键是问题的划分和base case。

问题分解

先判断根结点的整颗树是否满足二叉搜索树左小右大的规律,再判断各个子树是否同样满足这种规律。

判断准则

在后序遍历得到的序列中, 最后一个数字是树的根结点的值。
数组中前面的数字可以分为两部分

  1. 第一部分是左子树结点的值,它们都比根结点的值小
  2. 第二部分是右子树结点的值,它们都比根结点的值大。

代码实现

public class _33 {
    public static boolean verifySequenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length < 1) {
            return false;
        }
        return verifySequenceOfBST(sequence, 0, sequence.length - 1);
    }

    private static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
        // 如果对应要处理的数据只有一个或者已经没有数据要处理(start>end)就返回true
        if (start >= end) {// base case
            return true;
        }
        int index = start;
        while (index < end - 1 && sequence[index] < sequence[end]) {// 找右子树开始位置
            index++;
        }
        int right = index;// 记录下来。right为右子树开始的节点

        // 从右子树起点接着走,右子树的值都应该大于根节点
        while (index < end - 1 && sequence[index] > sequence[end]) {
            index++;// 应该要走到根节点前面 end-1
        }
        if (index != end - 1) {
            return false;// 说明根结点的右子树中有小于等于根结点的元素
        }
        return verifySequenceOfBST(sequence, start, right - 1) && verifySequenceOfBST(sequence, index, right - 1);
    }

    public static void main(String[] args) {
        //      8
        //    /  \
        //    6   10
        //   /\   /\
        //   5 7 9 11
        int[] sequence1 = { 5, 7, 6, 9, 11, 10, 8 };
        int[] sequence2 = { 7, 4, 6, 5 };
        System.out.println(verifySequenceOfBST(sequence1));// ture
        System.out.println(verifySequenceOfBST(sequence2));// false
    }
}

输出:

true
false
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题干 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假...
    懒人成长阅读 301评论 0 0
  • 目录 1、什么是树 2、相关术语 3、二叉树 3.1、二叉树的类型 3.2、二叉树的性质 3.3、二叉树的结构 3...
    我哈啊哈啊哈阅读 2,588评论 0 10
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 6,004评论 0 13
  • 周日,生日,520 这是属于我的日子 庆幸自己被深深爱着 感恩(≧∇≦)
    一个小酒窝啊阅读 143评论 0 0
  • “叮~宿主,你还好吧。”“嗯?”黎扬臻柒手捂着头,什么鬼?宿主是什么东西,好奇怪的词语。“你还歹回小爷一句话啥!哼...
    不爱不唯阅读 140评论 0 0