1，问题描述
题目描述：
给定一个以顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历方式将此部分树（不包含叶子）输出。
1、只有一个节点的树，此节点认定为根节点（非叶子）。
2、此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子或者无右叶子的情况
其他说明：二叉树的后序遍历是基于根来说的，遍历顺序为：左-右-根
输入描述
一个通过空格分割的整数序列字符串
输出描述
非叶子部分树结构
示例 1：
输入
输出
说明
找到非叶子部分树结构，然后采用后序遍历输出
2，初步思考
1，直接使用map来缓存节点，方便存取
2，依据层序遍历，整合出正确的二叉树
整合过程中舍弃没有叶子结点的节点
3，直接后续递归遍历即可
3，代码处理
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
| import java.util.*;
public class code1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
List<Integer> ints = new ArrayList<>();
String a = in.nextLine();
String[] split = a.split(" ");
for (int i = 0; i < split.length; i++) {
ints.add(Integer.parseInt(split[i]));
}
int n = ints.size();
if (n == 0) {
return;
}
if (n == 1) {
System.out.println(ints.get(0));
return;
}
Map<Integer, NodeList> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(i + 1, new NodeList(ints.get(i)));
}
int idx = 1;
while (idx <= n) {
int idxCur = idx * 2;
if (idxCur <= n && (idxCur * 2) <= n) {
map.get(idx).left = map.get(idxCur);
idxCur++;
if (idxCur <= n && (idxCur * 2) <= n) {
map.get(idx).right = map.get(idxCur);
}
}
idx++;
}
backforward(map.get(1));
for (Integer re : res) {
System.out.print(re + " ");
}
}
static List<Integer> res = new ArrayList<>();
private static void backforward(NodeList root) {
if (root == null) return;
backforward(root.left);
backforward(root.right);
res.add(root.val);
}
}
class NodeList {
int val;
NodeList left;
NodeList right;
public NodeList(int val) {
this.val = val;
}
}
|