102 Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal

1. Question

Given a binary tree, return thelevel ordertraversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree[3,9,20,null,null,15,7],
1
3
2
/ \
3
9 20
4
/ \
5
15 7
Copied!
return its level order traversal as:
1
[
2
[3],
3
[9,20],
4
[15,7]
5
]
Copied!

2. Implementation

(1) BFS
1
class Solution {
2
public List<List<Integer>> levelOrder(TreeNode root) {
3
List<List<Integer>> res = new ArrayList<>();
4
5
if (root == null) {
6
return res;
7
}
8
9
Queue<TreeNode> queue = new LinkedList<>();
10
List<Integer> level = new ArrayList<>();
11
queue.add(root);
12
13
while (!queue.isEmpty()) {
14
int size = queue.size();
15
level = new ArrayList<>();
16
17
for (int i = 0; i < size; i++) {
18
TreeNode curNode = queue.remove();
19
level.add(curNode.val);
20
21
if (curNode.left != null) {
22
queue.add(curNode.left);
23
}
24
25
if (curNode.right != null) {
26
queue.add(curNode.right);
27
}
28
}
29
res.add(level);
30
}
31
return res;
32
}
33
}
Copied!
(2) DFS
1
class Solution {
2
public List<List<Integer>> levelOrder(TreeNode root) {
3
List<List<Integer>> res = new ArrayList<>();
4
5
getLevelOrderByDFS(root, 0, res);
6
return res;
7
}
8
9
public void getLevelOrderByDFS(TreeNode node, int depth, List<List<Integer>> res) {
10
if (node == null) {
11
return;
12
}
13
14
if (res.size() == depth) {
15
res.add(new ArrayList<>());
16
}
17
18
res.get(depth).add(node.val);
19
20
getLevelOrderByDFS(node.left, depth + 1, res);
21
getLevelOrderByDFS(node.right, depth + 1, res);
22
}
23
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度:O(n) 空间复杂度:O(w)
DFS: 时间复杂度:O(n) 空间复杂度:O(h)