LinkedList saves the day : java simple solution


  • 0
    P

    The trick is to insert list of values of current level (listVals) to the head of linked list. (i.e. level.add(0, listVals)). But I wonder what is the time complexity of that operation. I am thinking if that is O(1) since the "level" list is implemented using LinkedList. Any different thought?

    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> level = new LinkedList<List<Integer>>();
            if (root == null) return level;
            
            List<TreeNode> frontier = new ArrayList<TreeNode>();
            frontier.add(root);
            while (!frontier.isEmpty()){
                List<Integer> listVals = new ArrayList();
                List<TreeNode> next = new ArrayList<TreeNode>();
                for (TreeNode curr: frontier){
                    listVals.add(curr.val);
                    
                    if (curr.left != null){
                        next.add(curr.left);
                    }
                    
                    if (curr.right != null){
                        next.add(curr.right);
                    }
                }
                
                // what is time complexity of this???
                level.add(0, listVals);
                frontier = next;
            }
            
            return level;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.