0102.md

102. Binary Tree Level Order Traversal

Level:

Topic:

Similar Problem:

• 199. Binary Tree Right Side View

Question

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Intuition

Iterative

• store every level nodes in a queue
• when traversing the current level, it corresponds to the current queue size
• just create a new list add add all current level node in when poll the queue

Recursive

• need to keep track of the level, so we know which level it corresponds to
• when to create a level list? when level == ans.size()

Code

Time: O(n)
Space: O(d), diameter of the level

Iterative

public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();

    List<List<Integer>> ans = new ArrayList<>();
    if (root != null)
        q.add(root);

    while (!q.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int n = q.size();
        while (n-- > 0) {
            root = q.poll();
            level.add(root.val);
            if (root.left != null)
                q.add(root.left);
            if (root.right != null)
                q.add(root.right);
        }
        ans.add(level);
    }
    return ans;
}

Time: O(n)
Space: O(n)

Recursive

List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root != null)
        traverse(root, 0);
    return ans;
}

private void traverse(TreeNode root, int level) {
    if (ans.size() == level)
        ans.add(new ArrayList<>());

    ans.get(level).add(root.val);

    if (root.left != null)
        traverse(root.left, level+1);
    if (root.right != null)
        traverse(root.right, level+1);
}