Question
给出一个二叉树，输出每一列的垂直和。 假设节点的左，右子与父节点成45度角。
例如，垂直和显示在下面的二叉树中
1
/
2 3
/
5 6
/
7 8
第一列和为9，第二列和为6，第三列和为11，第四列和为6
输出格式：1 2 3 4
购买提示
Code
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
|
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
class Nodes {
int data;
Nodes left, right;
Nodes(int item) {
data = item;
left = right = null;
}
}
public class A036 {
Nodes root;
public void print(Nodes node, int dist, Map<Integer, List<Integer>> map) {
if (node == null)
return;
if (!map.containsKey(dist)){
List<Integer> list = new ArrayList<>();
list.add(node.data);
map.put(dist, list);
}else {
map.get(dist).add(node.data);
}
print(node.left, dist - 1, map);
print(node.right, dist + 1, map);
}
public static void main(String[] args) {
A036 tree = new A036();
Map<Integer, List<Integer>> map = new TreeMap<>();//TreeMap保证添加进去的顺序
tree.root = new Nodes(1);
tree.root.left = new Nodes(2);
tree.root.right = new Nodes(3);
tree.root.right.left = new Nodes(5);
tree.root.right.right = new Nodes(6);
tree.root.right.left.left = new Nodes(7);
tree.root.right.left.right = new Nodes(8);
tree.print(tree.root, 0, map);
List<Integer>a=new ArrayList<Integer>();
for (List<Integer> value : map.values()) {
int sum=0;
for(int x=0;x<value.size();x++) {
sum+=value.get(x);
}
a.add(sum);
}
//System.out.println("第一列和为"+a.get(0)+"，第二列和为"+a.get(1)
//+"，第三列和为"+a.get(2)+"，第四列和为"+a.get(3));
System.out.println(a.get(0)+" "+a.get(1)+" "+a.get(2)+" "+a.get(3));
}
}
|
近期评论