102. Binary Tree Level Order Traversal

//O(n) time and space
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList();
        if(root==null) return list;
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        while(!q.isEmpty()){
            int level = q.size();
            List<Integer> sublist = new ArrayList();
            for(int i=0;i<level;i++){
                TreeNode temp = q.poll();
                sublist.add(temp.val);
                if(temp.left!=null) q.offer(temp.left);
                if(temp.right!=null) q.offer(temp.right);
            }
            list.add(sublist);
        }
        return list;
    }
}

//O(n) time and space recursive solution
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList();
        helper(list,root,0);
        return list;
    }
    
    public void helper(List<List<Integer>> list, TreeNode root, int start){
        if(root==null) return;
        if(list.size()<=start){
            list.add(new ArrayList());
        }
        list.get(start).add(root.val);
        helper(list,root.left,start+1);
        helper(list,root.right,start+1);
    }
}