Question
给定一个二叉树，写一个有效的算法来输出从根节点到每个叶节点的所有路径。
例如，考虑下面的二叉树
1
/
2 3
/ /
4 5 6 7
/
8 9
输出格式：
有X个从根节点到叶子节点的路径:
1 2 4
…
…
(其中X为阿拉伯数字)
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
55
56
57
58
|
import java.util.LinkedList;
class Nodes {
int data;
Nodes left, right;
Nodes(int item) {
data = item;
left = right = null;
}
}
public class A035 {
static int x=0;
public static int count(Nodes root) {
if (root != null) {
if(root.right==null&&root.left==null) {
x++;
}
count(root.left);//2-4,2-5;
count(root.right);//3-6(6-8),3-7(7-9);
}
return x;
}
public static void getPath(Nodes root){
if(root==null) return;
LinkedList<Nodes> list = new LinkedList<>();
getpathcore(root,list);
}
private static void getpathcore(Nodes root, LinkedList<Nodes> list) {
if(root==null) return;
list.add(root);
if(root.left==null&&root.right==null){
for(Nodes temp:list){
System.out.print(temp.data+" ");
}
System.out.println();
list.removeLast();
return;
}
getpathcore(root.left,list);
getpathcore(root.right,list);
list.removeLast();//返回时一定要清除
}
public static void main(String[] args) {
Nodes root = new Nodes(1);
root.left = new Nodes(2);
root.right = new Nodes(3);
root.left.left = new Nodes(4);
root.left.right = new Nodes(5);
root.right.left = new Nodes(6);
root.right.right = new Nodes(7);
root.right.left.left = new Nodes(8);
root.right.right.right = new Nodes(9);
x=count(root);
System.out.println("有"+x+"个从根节点到叶子节点的路径:");
getPath(root);
}
}
|
近期评论