题目描述
给定一棵二叉树的前序（根、左、右）和中序（左、根、右）的打印结果，输出此二叉树按层（从左往右）打印结果。
例如一棵二叉树前序：1 2 4 5 3；中序：4 2 5 1 3。可以构建出下图所示二叉树：
1
/
2 3
/
4 5
按层打印的结果则为：1 2 3 4 5。
思路
根据序列还原二叉树，再层次遍历。
1、根据前序还原1-2-4
2、对后面的节点（5、3）依次添加到二叉树，添加规则：
找到节点i在中序的下标，从后往前遍历其左边的元素，当发现左边的节点j在已经还原的二叉树中时（其一定是节点i的根节点），根据节点i在节点j的左侧还是右侧（由中序可以判断得到），就可以将节点i添加到二叉树正确的位置
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| import java.util.ArrayList;
import java.util.Scanner;
public class Main {
// 定义节点
class Node{
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
public ArrayList<Integer> gzy; // 保存根左右的序列
public ArrayList<Integer> zgy; // 保存左跟右的序列
public ArrayList<Node> pack; // 保存已经排好的节点
public static void main(String[] args) {
Main main = new Main();
main.getResult();
}
public void getResult() {
// init
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
gzy = new ArrayList<>();
zgy = new ArrayList<>();
for(int i = 0; i < count; i++) {
gzy.add(scanner.nextInt());
}
for(int j = 0; j < count; j++) {
zgy.add(scanner.nextInt());
}
pack = new ArrayList<>(); // 已经还原的节点
// exception
if(count == 1) {
System.out.println(gzy.get(0));
return;
}
// 构造最左侧节点的二叉树
Node node = new Node(gzy.get(0));
pack.add(node);
int index1 = 1; // 根左右的下标
Node tmp = node;
while(gzy.get(index1) != zgy.get(0)) { // 如果没访问到最左边的叶子节点,继续还原最左侧二叉树
tmp.left = new Node(gzy.get(index1++));
tmp = tmp.left;
pack.add(tmp);
}
tmp.left = new Node(gzy.get(index1++));
pack.add(tmp.left);
// 加入剩余的节点完善二叉树
for(int k = index1; k < gzy.size(); k++) {
fillErCS(gzy.get(k));
}
// 层次遍历
ArrayList<Node> res = new ArrayList<>();
res.add(node);
int num = 0;
while(res.size() != num) {
System.out.print(res.get(num).val + " ");
if(res.get(num).left != null) {
res.add(res.get(num).left);
}
if(res.get(num).right != null) {
res.add(res.get(num).right);
}
num++;
}
}
// 将值为val的节点加入二叉树
private void fillErCS(int val) {
int index = zgy.indexOf(val);
// 每一个遍历的节点都是val节点的根或者在其左边
for(int i = index-1; i >= 0; i--) {
if(findNode(zgy.get(i)) != null) { // 找到待插入节点的根节点或者其左边的节点
Node node = findNode(zgy.get(i));
insert(node, val);
break;
}
}
}
// 将节点val插入二叉树
private void insert(Node node, int val) {
if(zgy.indexOf(node.val) > zgy.indexOf(val)) { // node在待插入节点的右边
if(node.left == null) {
node.left = new Node(val);
pack.add(node.left);
return;
}
insert(node.left, val);
}else { // node在待插入节点的左边或是其根
if(node.right == null) {
node.right = new Node(val);
pack.add(node.right);
return;
}
insert(node.right, val);
}
}
// 根据val找到pack里的节点
private Node findNode(int val) {
for(Node node : pack) {
if(node.val == val) {
return node;
}
}
return null;
}
}
|
考察点