1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> ans = new ArrayList<>();
helper(root, ans, 0);
return ans;
}
private void helper(Node node, List<List<Integer>> ans, int level) {
if (node == null) {
return;
}
if (level == ans.size()) {
ans.add(new ArrayList<>());
}
ans.get(level).add(node.val);
for (Node child : node.children) {
helper(child, ans, level + 1);
}
}
}
|
DFS.
时间复杂度: O(n)
空间复杂度: O(h) h是树的高度, 最worst就是skewed tree也就是O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<List<Integer>> levelOrder(Node root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
Deque<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> currLayer = new ArrayList<>();
for (int i = q.size(); i > 0; i--) {
Node currNode = q.poll();
currLayer.add(currNode.val);
q.addAll(currNode.children);
}
ans.add(currLayer);
}
return ans;
}
}
|
BFS的做法.
时间复杂度: O(n)
空间复杂度: O(n)
