JAVA SOLUTION WITH LINKEDLIST


  • 12

    This solution is nearly identical to the traditional 'Level Order traversal' only difference is the DataStructure used to hold the data. Instead of Using an ArrayList and appending each level after the other I used a LinkedList and added each new level to the head of the LinkedList.

    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            if(root == null) return new LinkedList<List<Integer>>();
            List<List<Integer>> levels = new LinkedList<List<Integer>>();
            Queue<TreeNode> q = new LinkedList<TreeNode>(); 
            q.add(root);
            
            while(!q.isEmpty()){
                List<Integer> list = new ArrayList<Integer>(); 
                int size = q.size();
                for(int i = 0; i < size; i++){
                    TreeNode node = q.remove();
                    list.add(node.val);
                    if(node.left != null) q.add(node.left);
                    if(node.right != null) q.add(node.right);
                }
                ((LinkedList)levels).addFirst(list);
            }
            return levels;
        }
    }

  • 0
    D

    great soluton,

    but could you tell more about type cast?
    why 2 brackets could let list interface object to use addFirst() function?
    according to documentation, it seems addFirst() is for Deque interface only

      ((LinkedList)levels).addFirst(list);

  • 0
    1. The Double braces are needed because this forces the cast to be done on levels making it a LinkedList first then taking that casted LinkedList and calling addFirst on it. You were probably expected to see this (LinkedList)levels.addFirst(list) but what that says is cast the result of levels.addFirst(list) to a LinkedList but that doesn't make sense and isn't what we want you cant cast the result of levels.addFirst(list) because it doesn't even return anything.

    2. As you stated the reason for the cast is because List Interface doesn't have a addFirst So I needed to cast to a LinkedList which does have it. I'm fairly confident if I were to make levels a Deque<List<Integers>> then the cast wouldn't be needed at all, as you mentioned it would use it from the Deque Interface.

    3. So we can't use Deque because of the problem constraints. LeetCode wants the return to be List<List<Integer>> so we are stuck with it


  • 0
    D

    thanks for your detailed explanation. I was initially confused about whether linkedlist would categorize as a type. Speak of type case, I thought queue/deque/list would be types but linkedlist is just implementation of all those interface. :(


  • 0

    You have it exactly correct LinkedList Implements all three of those Interfaces. Let me know if you need anything else


  • 0
    D

    so far so good . thanks :)


  • 0
    A

    Instead of casting List<List<Integer>> to LinkedList for every level of nodes, you can simple declare LinkedList<List<Integer>> levels = new LinkedList<List<Integer>>();


Log in to reply
 

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