package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/binary-tree-level-order-traversal/
 */
public class Problem102 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        class LevelNode {
            int level;
            TreeNode node;

            public LevelNode(int level, TreeNode node) {
                this.level = level;
                this.node = node;
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        LinkedList<LevelNode> linkedList = new LinkedList<>();
        linkedList.add(new LevelNode(0, root));
        while (!linkedList.isEmpty()) {
            LevelNode n = linkedList.removeFirst();
            if (!map.containsKey(n.level)) {
                List<Integer> list = new ArrayList<>();
                list.add(n.node.val);
                map.put(n.level, list);
            } else {
                map.get(n.level).add(n.node.val);
            }
            if (n.node.left != null) {
                linkedList.addLast(new LevelNode(n.level + 1, n.node.left));
            }
            if (n.node.right != null) {
                linkedList.addLast(new LevelNode(n.level + 1, n.node.right));
            }
        }
        for (int i = 0; i < map.size(); i++) {
            result.add(map.get(i));
        }
        return result;
    }
}

@@ -44,34 +44,8 @@
 st;%0A
-import java.util.HashMap;%0A
 impo
@@ -95,30 +95,8 @@
 ist;
-%0Aimport java.util.Map;
 %0A%0A/*
@@ -422,237 +422,8 @@
 ) %7B%0A
-        class LevelNode %7B%0A            int level;%0A            TreeNode node;%0A%0A            public LevelNode(int level, TreeNode node) %7B%0A                this.level = level;%0A                this.node = node;%0A            %7D%0A        %7D%0A%0A
     
@@ -543,67 +543,8 @@
   %7D%0A
-        Map%3CInteger, List%3CInteger%3E%3E map = new HashMap%3C%3E();%0A
     
@@ -562,29 +562,23 @@
 ist%3C
-Level
+Tree
 Node%3E 
-linkedList
+queue
  = n
@@ -608,46 +608,23 @@
     
-linkedList.add(new LevelNode(0, 
+queue.add(
 root)
-)
 ;%0A  
@@ -637,26 +637,21 @@
 while (!
-linkedList
+queue
 .isEmpty
@@ -673,311 +673,143 @@
    L
-evelNode n = linkedList.removeFirst();%0A            if (!map.containsKey(n.level)) %7B%0A                List%3CInteger%3E list = new ArrayList%3C%3E();%0A                list.add(n.node.val);%0A                map.put(n.level, list);%0A            %7D else %7B%0A                map.get(n.level).add(n.node.val);%0A        
+ist%3CInteger%3E list = new ArrayList%3C%3E();%0A            int queueSize = queue.size();%0A            for (int i = 0; i %3C queueSize; i++) %7B%0A
     
-%7D%0A
     
@@ -820,22 +820,28 @@
     if (
-n.node
+queue.peek()
 .left !=
@@ -869,67 +869,40 @@
     
-linkedList.addLast(new LevelNode(n.level + 1, n.node
+    queue.add(queue.peek()
 .left)
-)
 ;%0A  
@@ -903,34 +903,42 @@
 t);%0A            
+ 
-%7D%0A
+   %7D%0A    
             if (
@@ -937,22 +937,28 @@
     if (
-n.node
+queue.peek()
 .right !
@@ -987,68 +987,41 @@
     
-linkedList.addLast(new LevelNode(n.level + 1, n.node
+    queue.add(queue.peek()
 .right)
-)
 ;%0A  
@@ -1018,38 +1018,32 @@
 right);%0A        
-    %7D%0A
         %7D%0A      
@@ -1048,46 +1048,57 @@
     
-for (int i = 0; i %3C map.size(); i++) %7B
+        list.add(queue.poll().val);%0A            %7D
 %0A   
@@ -1121,18 +1121,12 @@
 add(
-map.get(i)
+list
 );%0A 

Update problem 102