[2018-Interview] Binary Tree Level Order Traversal

Original question: https://leetcode.com/problems/binary-tree-level-order-traversal/description/

My Answer:

Iteration:

/**
 * 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>> allNodes = new ArrayList<List<Integer>>();
        if (root == null) {
            return allNodes;
        }
        List<TreeNode> currentLevel = new ArrayList<TreeNode>();
        currentLevel.add(root);
        int currentLevelSize = currentLevel.size();
        int nextLevelSize = 0;
        while(!currentLevel.isEmpty()) {
            List<Integer> values = new ArrayList<Integer>();
            while (currentLevelSize > 0) {
                TreeNode node = currentLevel.get(0);
                currentLevel.remove(0);
                values.add(node.val);
                if (node.left != null) {
                    currentLevel.add(node.left);
                    nextLevelSize ++;
                }
                if (node.right != null) {
                    currentLevel.add(node.right);
                    nextLevelSize ++;
                }
                currentLevelSize --;
            }
            allNodes.add(values);
            currentLevelSize = nextLevelSize;
            nextLevelSize = 0;
        }
        
        return allNodes;
    }
}

Recursion:

/**
 * 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>> allNodes = new ArrayList<List<Integer>>();
        if (root == null) {
            return allNodes;
        }
        helper(root, 0, allNodes);
        
        return allNodes;
    }

    void helper(TreeNode node, int level, List<List<Integer>> allNodes) {
        if (node == null) {
            return;
        }

        List<Integer> values = new ArrayList<Integer>();
        values.add(node.val);

        if (allNodes.size() > level) {
            List<Integer> existingValues = allNodes.get(level);
            existingValues.addAll(values);
            allNodes.remove(level);
            allNodes.add(level, existingValues);
        } else {
            allNodes.add(values);
        }
        
        helper(node.left, level + 1, allNodes);
        helper(node.right, level + 1, allNodes);
    }
}