文档章节

【九度OJ1385】|【剑指offer6】重建二叉树

aqia358
 aqia358
发布于 2013/11/28 11:35
字数 640
阅读 58
收藏 1
点赞 0
评论 0

题目描述:

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。

输入:

输入可能包含多个测试样例,对于每个测试案例,

输入的第一行为一个整数n(1<=n<=1000):代表二叉树的节点个数。

输入的第二行包括n个整数(其中每个元素a的范围为(1<=a<=1000)):代表二叉树的前序遍历序列。

输入的第三行包括n个整数(其中每个元素a的范围为(1<=a<=1000)):代表二叉树的中序遍历序列。

输出:

对应每个测试案例,输出一行:

如果题目中所给的前序和中序遍历序列能构成一棵二叉树,则输出n个整数,代表二叉树的后序遍历序列,每个元素后面都有空格。

如果题目中所给的前序和中序遍历序列不能构成一棵二叉树,则输出”No”。

样例输入:
8
1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
8
1 2 4 7 3 5 6 8
4 1 2 7 5 3 8 6
样例输出:
7 4 2 5 8 6 3 1 
No
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

public class Main {

	private int[] pre;
	private int[] mid;
	private List<Integer> list = new ArrayList<Integer>();
	
	class Node {
		private Node left;
		private Node right;
		private int data;

		public Node(int data) {
			this.data = data;
			left = null;
			right = null;
		}
	}
	public int find(int data, int start, int end) {
		for (int i = start; i <= end; i++) {
			if (mid[i] == data) {
				return i;
			}
		}
		return -1;
	}

	public Node build(int pIndex, int mStart, int mEnd) {
		if(pIndex >= pre.length)return null;
		int mIndex = find(pre[pIndex], mStart, mEnd);
		if (mIndex == -1 || pIndex + mIndex - mStart + 1 > pre.length) {
			return null;
		}
		if (mStart == mEnd) {
			return new Node(mid[mStart]);
		}
		Node node = new Node(pre[pIndex]);
		node.left = build(pIndex + 1, mStart, mIndex - 1);//左节点的根为pIndex + 1
		node.right = build(pIndex + mIndex - mStart + 1, mIndex + 1, mEnd);//右节点的根为pIndex + mIndex - mStart + 1
		return node;
	}

	public void postOrder(Node root){
		if(root.left !=null)postOrder(root.left);
		if(root.right != null)postOrder(root.right);
		list.add(root.data);
	}
	public void print(){
		if(pre.length > list.size()){
			System.out.println("No");
		}else{
			for(int i = 0; i < list.size(); i++){
				System.out.print(list.get(i)+" ");
			}
			System.out.println();
		}
	}
	public void run(int n) {
		postOrder(build(0, 0, n - 1));
		print();
	}

	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != StreamTokenizer.TT_EOF){
			int n = (int)st.nval;
			int count = 0;
			Main m = new Main();
			m.pre = new int[n];
			m.mid = new int[n];
			while(count < n && st.nextToken() != st.TT_EOF)m.pre[count++] = (int)st.nval;
			count = 0;
			while(count < n && st.nextToken() != st.TT_EOF)m.mid[count++] = (int)st.nval;
			m.run(n);
		}
	}
}








© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
剑指Offer学习总结-重建二叉树

剑指Offer学习总结-重建二叉树 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163.co...

wwlcsdn000 ⋅ 01/16 ⋅ 0

算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴 ⋅ 2017/11/08 ⋅ 0

剑指Offer——知识点储备-常用算法

剑指Offer——知识点储备-常用算法 快速排序 注:若排序是有序的,采用快排,则退化为冒泡排序。 解决这个问题,采用两个选取基准的方法 (1)随机选取基数(在这个区间内随机取一个数) 出现...

sunhuaqiang1 ⋅ 2016/11/07 ⋅ 0

剑指Offer-根据二叉树的前序和后序遍历重建二叉树

原文地址:点击打开链接 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8} 和...

z956281507 ⋅ 2017/12/13 ⋅ 0

【剑指Offer】重建二叉树——JavaScript实现

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,...

highboys ⋅ 2017/11/27 ⋅ 0

python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905 ⋅ 06/03 ⋅ 0

【九度OJ1521】|【剑指offer19】二叉树的镜像

题目描述: 输入一个二叉树,输出其镜像。 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数(节...

aqia358 ⋅ 2013/12/18 ⋅ 0

【数据结构】树的基本内容总结

课程正式开始了。因为有些课感觉好没意思。恰好,背着数据结构(c语言版)去上算法课,于是从那次开始看。慢慢的看的还挺有意思,于是把树这章基本看完了,做个小结。、 因为普通的树应用价值...

shewa ⋅ 2012/09/11 ⋅ 0

Redis研究-3.3数据结构之树与查找、排序等

1.树相关的内容 1.1 Tree概念 树是n(n>=0)个节点的有限集。n=0的时候,我们把它叫做空树。在任何一非空树中满足两个特点:(1)有且只有一个叫做根的节点。(2)n>1时,其余节点可分为m(m>0...

会飞的杨先生 ⋅ 2015/08/26 ⋅ 0

数据结构-二叉树的存储结构与遍历

定义 一个有穷的结点集合,可以为空。若不为空,则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。 二叉树的五种基本形态: tree_state 二叉树的子树是有顺序之分的,称为左...

IAM四十二 ⋅ 2017/10/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java NIO之字符集

1 字符集和编解码的概念 首先,解释一下什么是字符集。顾名思义,就是字符的集合。它的初衷是把现实世界的符号映射为计算机可以理解的字节。比如我创造一个字符集,叫做sex字符集,就包含两个...

士别三日 ⋅ 29分钟前 ⋅ 0

Spring Bean基础

1、Bean之间引用 <!--如果Bean配置在同一个XML文件中,使用local引用--><ref bean="someBean"/><!--如果Bean配置在不同的XML文件中,使用ref引用--><ref local="someBean"/> 其实两种......

霍淇滨 ⋅ 35分钟前 ⋅ 0

05、基于Consul+Upsync+Nginx实现动态负载均衡

1、Consul环境搭建 下载consul_0.7.5_linux_amd64.zip到/usr/local/src目录 cd /usr/local/srcwget https://releases.hashicorp.com/consul/0.7.5/consul_0.7.5_linux_amd64.zip 解压consu......

北岩 ⋅ 38分钟前 ⋅ 0

Webpack 4 api 了解与使用

webpack 最近升级到了 v4.5+版 01 官方不再支持 node4 以下版本 官方不再支持 node4 以下版本官方不再支持 node4 以下的版本,所以如果你的node版本太低,先开始升级node吧!话说node10 ...

NDweb ⋅ 47分钟前 ⋅ 0

使用nodeJs安装Vue-cli

Vue脚手架就是一个Vue框架开发环境 脚手架的意思是帮你快速开始一个vue的项目,也就是给你一套vue的结构,包含基础的依赖库,只需要 npm install就可以安装,让我们不需要为了编辑或者一些其...

木筏笔歆 ⋅ 今天 ⋅ 0

【微信小程序开发实战】0x00.开发前准备工作

写在开始 本人资深后端码农一枚,近期项目需求,接触到了微信小程序,将学习过程整理成文分享给小伙伴们,由于是边学边整理难免有表述不对的地方,望大家及时指正,感谢。 本人微信号: dream...

dreamans ⋅ 今天 ⋅ 0

linux redis的安装和php7下安装redis扩展

安装redis服务器 (1)下载安装包: $ wget http://download.redis.io/releases/redis-2.8.17.tar.gz (2)编译程序: $ tar xzf redis-2.8.17.tar.gz $ cd redis-2.8.17 $ make $ cd src &&......

concat ⋅ 今天 ⋅ 0

Guava EventBus源码解析

一、EventBus使用场景示例 Guava EventBus是事件发布/订阅框架,采用观察者模式,通过解耦发布者和订阅者简化事件(消息)的传递。这有点像简化版的MQ,除去了Broker,由EventBus托管了订阅&...

SaintTinyBoy ⋅ 今天 ⋅ 0

http怎么做自动跳转https

Apache 版本 如果需要整站跳转,则在网站的配置文件的<Directory>标签内,键入以下内容: RewriteEngine on RewriteCond %{SERVER_PORT} !^443$ RewriteRule ^(.*)?$ https://%{SERVER_NAME......

Helios51 ⋅ 今天 ⋅ 0

Python爬虫,抓取淘宝商品评论内容

作为一个资深吃货,网购各种零食是很频繁的,但是能否在浩瀚的商品库中找到合适的东西,就只能参考评论了!今天给大家分享用python做个抓取淘宝商品评论的小爬虫! 思路 我们就拿“德州扒鸡”...

python玩家 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部