LinkedList saves the day : java simple solution

  • 0

    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>();
            while (!frontier.isEmpty()){
                List<Integer> listVals = new ArrayList();
                List<TreeNode> next = new ArrayList<TreeNode>();
                for (TreeNode curr: frontier){
                    if (curr.left != null){
                    if (curr.right != null){
                // 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.