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)

101 Symmetric Tree

103 Binary Tree Zigzag Level Order Traversal

Last modified 2yr ago

Copy link

Contents

102. Binary Tree Level Order Traversal

1. Question

2. Implementation

3. Time & Space Complexity