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

aqia358

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.IOException;
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);
}
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

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

09/04
0
0

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

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

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的二级缓存

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

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问题排查也不是很难--工具使用

java_龙
21分钟前
4
0