文档章节

IT公司100题-9-判断整数序列是不是二元查找树的后序遍历结果

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/11/05 16:46
字数 395
阅读 72
收藏 4

问题描述:

输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回true,否则返回false。

例如输入4, 8, 6, 12, 16, 14, 10,由于这一整数序列是如下树的后序遍历结果:

 10
/     \
6      14
/  \    /   \
4   8 12    16

因此返回true。

如果输入6, 5, 8, 5, 7 ,则返回false。

 问题分析:

在后续遍历得到的序列中,最后一个元素为树的根结点。根节点元素将数组分为两部分,左边都小于根节点,右边都大于根节点。递归的确认左右是否是二元查找树即可。

代码实现:

/**
 * @project: oschina
 * @filename: IT9.java
 * @version: 0.10
 * @author: JM Han
 * @date: 8:40 2015/11/5
 * @comment: Test Purpose
 * @result:
 */

import static tool.util.*;

public class IT9 {
   static boolean verify(int start, int end, int[] a){
      //只有一个元素时 = ,返回true
      //左子树不存在是 > , 返回true
      if(start >= end)
         return true;

      int i; int j;
      for(i = start; a[i] < a[end]; i++);
      for(j = i; a[j] > a[end]; j++);

      //左子树和右子树加上root可以遍历完此部分数组,否则不是BST
      if(j != end)
         return false;

      boolean right = verify(start, i-1, a);
      boolean left = verify(i, j - 1, a);

      //进当左右子树都符合条件返回true
      if(right && left)
         return true;

      return false;
   }

   public static void main(String[] args) {
      //int[] a = new int[]{4,8,6,12,16,14,10};
      //int[] a = new int[]{4,8,6,12,16,11,10};
      //int[] a = new int[]{4,8,6,9,11,12,10};
      //int[] a = new int[]{4,8,6,12,9,11,10};
      boolean res = verify(0, a.length-1, a);
      String isn = res?"is":"isn't";
      System.out.println("Array " + isn + " a tree of postorder tranversal");
   }
}


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
判断整数序列是不是二元查找树的后序遍历结果

判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回 true,否则返回 false。 例如输入 5、7、6、9、11、10、...

Zhang_H
2014/04/17
374
0
【6】判断整数序列是不是二元查找树的后序遍历结果

/* 判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、...

SibylY
2016/07/31
51
0
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 1...

云栖希望。
2017/12/04
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
判断一个数组是否为后序遍历结果

输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 思路一: 中序遍历为增长数组,判断是否矛盾 思路二: 如5、7、6、9、11、10、8 代码编...

datacube
2016/08/03
14
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈FlyWeight享元模式

一、前言 享元(FlyWeight)模式顾名思义,即是轻量级,原因就是享元,共享元素,这里的元素指的是对象。如何共享对象,那就是在检测对象产生的时候,如果产生的是同一个对象,那么直接使用已...

青衣霓裳
18分钟前
3
0
Python学习10.14:Python set集合详解

Python 中的集合,和数学中的集合概念一样,用来保存不重复的元素,即集合中的元素都是唯一的,互不相同。 从形式上看,和字典类似,Python 集合会将所有元素放在一对大括号 {} 中,相邻元素...

太空堡垒185
18分钟前
5
0
好程序员大数据教程分享Scala系列之文件以及正则表达式

好程序员大数据教程分享Scala系列之文件以及正则表达式 1 读取行 导入scala.io.Source后,即可引用Source中的方法读取文件信息。 import scala.io.Source object FileDemo extends App{ val ...

好程序员官网
19分钟前
4
0
75.nosql memcached与安装及查看状态

21.1 nosql介绍 21.2 memrcached介绍 21.3 安装memcached 21.4 查看memcachedq状态 21.1 nosql介绍 什么是NoSQL: 1.非关系型数据库就是NoSQL,关系型数据库代表MySQL 也是一种数据库,来存储...

oschina130111
21分钟前
3
0
玩转阿里云 Terraform(二):Terraform 的几个关键概念

上一篇《玩转阿里云Terraform(一):Terraform 是什么》介绍了 Terraform 的基本定义和特点之后,本文将着重介绍几个Terraform中的关键概念。 Terraform 关键概念 在使用Terraform的过程中,通...

阿里云官方博客
21分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部