文档章节

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

aqia358
 aqia358
发布于 2013/11/28 11:35
字数 640
阅读 60
收藏 1

题目描述:

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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
博文 82
码字总数 30297
作品 0
海淀
程序员
私信 提问
剑指Offer学习总结-重建二叉树

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

wwlcsdn000
01/16
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
剑指offer 5. 二叉树的下一个节点

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

dby_freedom
10/16
0
0
[剑指offer] 重建二叉树

本文首发于我的个人博客:尾尾部落 题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,...

繁著
08/09
0
0
【挑战剑指offer】系列04:重建二叉树

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

LinkedBear
11/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

控制台打印图片

function dev(){ if (window.console){ console.log("%c\n ", "font-size:100px;background:url('http://gmcyzs.com/resources/images/logo.png') no-repeat"); console.log('%c 深务平台,\......

羊皮卷
11分钟前
0
0
MyBaties的二级缓存

二级缓存介绍 在上文中提到的一级缓存中,其最大的共享范围就是一个SqlSession内部,那么如何让多个SqlSession之间也可以共享缓存呢,答案是二级缓存。 当开启二级缓存后,会使用CachingExec...

嘴角轻扬30
11分钟前
2
0
10.新增博客功能-结束语---《Beetl视频课程》

本期视频实现发布新博客功能 一起学beetl目录:https://my.oschina.net/u/1590490?tab=newest&catalogId=6214598 作者:GK 教程进入了尾声,该讲的知识点基本讲到了,本节课不会讲新的知识点。...

Gavin-King
16分钟前
2
0
SpringBoot项目热部署

IntelliJ IDEA开发工具 1.需要在pom.xml文件中加入以下依赖。 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-devtools</artifactId> ......

llsydn
17分钟前
1
0
JVM问题排查也不是很难--工具使用

目录 概述 环境准备 工具介绍 远程连接方式 开启JMX 工具远程连接 参考文献 概述 线上环境中,程序越来越慢,一头雾水?遇到程序经常宕机,但找不到原因?排查问题却经常记不住命令? 那是没找到好...

java_龙
21分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部