package leetcode;

/**
 * https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
 */
public class Problem116 {
    public static class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;

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

    public void connect(TreeLinkNode root) {

    }
    
    public static void main(String[] args) {
        Problem116 prob = new Problem116();
        
        TreeLinkNode root = new TreeLinkNode(1);
        root.left = new TreeLinkNode(2);
        root.right = new TreeLinkNode(3);
        root.left.left = new TreeLinkNode(4);
        root.left.right = new TreeLinkNode(5);
        root.right.left = new TreeLinkNode(6);
        root.right.right = new TreeLinkNode(7);
        
        prob.connect(root);
        
        for (TreeLinkNode node = root.left; node != null; node = node.next) {
            System.out.println(node.val);
        }
        System.out.println("-------------------------------------------------");
        for (TreeLinkNode node = root.left.left; node != null; node = node.next) {
            System.out.println(node.val);
        }
    }
}

@@ -12,16 +12,118 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.LinkedList;%0Aimport java.util.Map;%0Aimport java.util.Queue;%0A%0A
 /**%0A * h
@@ -400,27 +400,79 @@
    p
-ublic void connect(
+rivate static class LevelNode %7B%0A        final int level;%0A        final 
 Tree
@@ -484,28 +484,27 @@
 ode 
-root) %7B%0A%0A
+node;%0A    
     
-%7D
 %0A    
-%0A
     
@@ -514,84 +514,110 @@
 lic 
-static void main(String%5B%5D args) %7B%0A        Problem116 prob = new Problem116()
+LevelNode(int level, TreeLinkNode node) %7B%0A            this.level = level;%0A            this.node = node
 ;%0A  
@@ -626,328 +626,560 @@
     
+%7D
 %0A    
+%7D%0A
     
-TreeLinkNode root = new TreeLinkNode(1);%0A        root.left = new TreeLinkNode(2);%0A        root.right = new TreeLinkNode(3);%0A        root.left.left = new TreeLinkNode(4);%0A        root.left.right = new TreeLinkNode(5);%0A        root.right.left = new TreeLinkNode(6);%0A        root.right.right = new TreeLinkNode(7);
+%0A    public void connect(TreeLinkNode root) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        Queue%3CLevelNode%3E queue = new LinkedList%3C%3E();%0A        queue.add(new LevelNode(1, root));%0A        Map%3CInteger, TreeLinkNode%3E map = new HashMap%3C%3E();%0A        while (!queue.isEmpty()) %7B%0A            LevelNode levelNode = queue.remove();%0A            int level = levelNode.level;%0A            TreeLinkNode left = levelNode.node.left;%0A            TreeLinkNode right = levelNode.node.right;%0A            if (left == null %7C%7C right == null) %7B
 %0A   
@@ -1183,25 +1183,24 @@
         
-%0A
         
 prob.con
@@ -1195,154 +1195,136 @@
     
-prob.connect(root);%0A        %0A        for (TreeLinkNode node = root.left; node != null; node = node.next) %7B%0A            System.out.println(node.val
+continue;%0A            %7D%0A            queue.add(new LevelNode(level+1, left));%0A            queue.add(new LevelNode(level+1, right)
 );%0A 
@@ -1334,99 +1334,59 @@
     
-%7D%0A
     
-    System.out.println(%22-------------------------------------------------%22);%0A
+if (map.containsKey(level+1)) %7B%0A       
         
 for 
@@ -1385,13 +1385,9 @@
     
-for (
+ 
 Tree
@@ -1406,97 +1406,139 @@
 e = 
-root.left.left; node != null; node = node.next) %7B%0A            System.out.println(node.val
+map.get(level+1);%0A                node.next = left;%0A            %7D%0A            left.next = right;%0A            map.put(level+1, right
 );%0A 

Solve problem 116