[LeetCode] 102. Binary Tree Level Order Traversal

Posted on | In

Problem

Given a binary tree, return the level order traversal 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
2
3
4
5
    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

Explanation 1

  1. We can use the BFS method. We store each layer’s values into a list, then add this list into the result. The problem now of the BFS is we don’t know the number of elements in each layer. To solve this, we need to record the size of each layer before we pop and push the left child and right child elements into the list, and we pop the number of elements base on this size.

  2. From the above example, we first push 3 into the queue, record the size is 1, then we pop 1 element adding to a list, then push its left and right child 9 and 20, now the queue has 2 elements, so we update the size to 2. Then we should pop 2 elements this time, we pop 9, pop 20, adding to a list, and push its left and right child 15 and 7. Now the queue has 2 elements, so we update its size to 2, and we only pop size=2 elements and adding to the list, etc, until the queue is empty.

Solution 1

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> lst = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                lst.add(temp.val);
                if (temp.left != null) queue.offer(temp.left);
                if (temp.right != null) queue.offer(temp.right);
            }
            res.add(lst);
        }

        return res;
    }
}

Explanation 2

We can also use DFS method to solve this problem.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    void helper(TreeNode root, List<List<Integer>> res, int level) {
        if (root == null) return;
        if (res.size() < level+1) res.add(new ArrayList<>());
        res.get(level).add(root.val);
        if (root.left != null) helper(root.left, res, level+1);
        if (root.right != null) helper(root.right, res, level+1);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) return res;
        helper(root, res, 0);
        return res;
    }
}