-
Notifications
You must be signed in to change notification settings - Fork 53
Expand file tree
/
Copy pathLeetCode_429_1.java
More file actions
133 lines (114 loc) · 3.75 KB
/
LeetCode_429_1.java
File metadata and controls
133 lines (114 loc) · 3.75 KB
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
120
121
122
123
124
125
126
127
128
129
130
131
132
package id_1;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* @创建人 luoxiang
* @创建时间 2019/6/19 12:25
* @描述 LeetCode : 429. N叉树的层序遍历 https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/submissions/
*/
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
public class LeetCode_429_1 {
public static void main(String[] args) {
final Node node5 = new Node(5, null);
final Node node6 = new Node(6, null);
final LinkedList<Node> nodes = new LinkedList<>();
nodes.add(node5);
nodes.add(node6);
final Node node3 = new Node(3, nodes);
final Node node2 = new Node(2, null);
final Node node4 = new Node(4, null);
final LinkedList<Node> nodes2 = new LinkedList<>();
nodes2.add(node3);
nodes2.add(node2);
nodes2.add(node4);
final Node root = new Node(1, nodes2);
final List<List<Integer>> lists = new LeetCode_429_1().levelOrder2(root);
for (List<Integer> list : lists) {
for (Integer integer : list) {
System.out.print(integer + ",");
}
System.out.println();
}
}
/**
* Method 1 : BFS 队列实现
* 时间复杂度 ： O(N)
* 空间复杂度 ： O(N)
*/
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> list = new LinkedList<>();
if (root == null) return list;
Queue<Node> queue = new LinkedList<>();
List<Integer> linkedList = new LinkedList<>();
queue.offer(root);
int currentSize = 1;
while (!queue.isEmpty()) {
Node node = queue.poll();
linkedList.add(node.val);
if (node.children != null) {
for (Node child : node.children) {
queue.offer(child);
}
}
if (--currentSize == 0) {
currentSize = queue.size();
list.add(linkedList);
linkedList = new LinkedList<>();
}
}
return list;
}
/**
* Method 2 : BFS 不在外层创建 临时的 List<Integer> , 在循环内部创建
*/
public List<List<Integer>> levelOrder2(Node root) {
List<List<Integer>> list = new LinkedList<>();
if (root == null) return list;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> linkedList = new LinkedList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
linkedList.add(node.val);
if (node.children != null) {
for (Node child : node.children) {
queue.offer(child);
}
}
}
list.add(linkedList);
}
return list;
}
public List<List<Integer>> levelOrder3(Node root) {
List<List<Integer>> ret = new LinkedList<>();
if (root == null) return ret;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> curLevel = new LinkedList<>();
int len = queue.size();
for (int i = 0; i < len; i++) {
Node curr = queue.poll();
curLevel.add(curr.val);
for (Node c : curr.children)
queue.offer(c);
}
ret.add(curLevel);
}
return ret;
}
}