Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Example:

1 2 3 4 5 6 7 8 9 10 11

3 / \ 920 / \ 157 Output: [ [3], [9,20], [15,7] ]

Analysis

Recursion (preorder)

Expand the result list if the current level is equal to the size of result list. Visiting a node involves putting its value to the corresponding array list of current level.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = newArrayList<>(); preorder(root, result, 0); return result; }

public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { // this check is required returnnewArrayList<>(); } List<List<Integer>> result = newArrayList<>(); Queue<TreeNode> queue = newLinkedList<>(); queue.offer(root); intlevel=0; while (queue.size() > 0) { // start the current level result.add(newArrayList<>());

// queue stores all nodes on the current level intlevelSize= queue.size(); for (inti=0; i < levelSize; ++i) { TreeNodenode= queue.poll(); result.get(level).add(node.val); // offer its children to the queue if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); }

++level; } return result; }

Time: $O(N)$ Space: $O(h + N)$ including result list.

Problem II

Return the bottom-up level order traversal.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> result = newLinkedList<>(); preorder(root, result, 0); return result; }