populating next right pointers in each node

fishercoder1534 · fishercoder1534 · commit 7332d369b1ee · 2016-10-05T11:05:49.000-07:00
diff --git a/MEDIUM/src/medium/PopulatingNextRightPointersinEachNode.java b/MEDIUM/src/medium/PopulatingNextRightPointersinEachNode.java
@@ -0,0 +1,60 @@
+package medium;
+import classes.TreeLinkNode;
+
+/**
+ * Created by fishercoder1534 on 10/5/16.
+ */
+public class PopulatingNextRightPointersinEachNode {
+    //copied this post: https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution
+    //very clever and concise to make it in O(1) space
+
+    //based on level order traversal
+    public static void connect(TreeLinkNode root) {
+
+        TreeLinkNode head = null; //head of the next level
+        TreeLinkNode prev = null; //the leading node on the next level
+        TreeLinkNode cur = root;  //current node of current level
+
+        while (cur != null) {
+
+            while (cur != null) { //iterate on the current level
+                //left child
+                if (cur.left != null) {
+                    if (prev != null) {
+                        prev.next = cur.left;
+                    } else {
+                        head = cur.left;
+                    }
+                    prev = cur.left;
+                }
+                //right child
+                if (cur.right != null) {
+                    if (prev != null) {
+                        prev.next = cur.right;
+                    } else {
+                        head = cur.right;
+                    }
+                    prev = cur.right;
+                }
+                //move to next node
+                cur = cur.next;
+            }
+
+            //move to next level
+            cur = head;
+            head = null;
+            prev = null;
+        }
+
+    }
+
+    public static void main(String...args){
+        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.right = new TreeLinkNode(7);
+        connect(root);
+    }
+}
diff --git a/README.md b/README.md
@@ -8,6 +8,8 @@
 |140|[Word Break II](https://leetcode.com/problems/word-break-ii/)|[Solution](../../blob/master/HARD/src/hard/WordBreakII.java)| ? |O(n^2) | Hard| Backtracking/DFS
 |139|[Word Break](https://leetcode.com/problems/word-break/)|[Solution](../../blob/master/MEDIUM/src/medium/WordBreak.java)| O(n^2)|O(n) | Medium| DP
 |133|[Clone Graph](https://leetcode.com/problems/clone-graph/)|[Solution](../../blob/master/MEDIUM/src/medium/CloneGraph.java)| O(n)|O(n) | Medium| HashMap, BFS 
+|117|[Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)|[Solution](../../blob/master/HARD/src/hard/PopulatingNextRightPointersinEachNodeII.java)| O(n)|O(1) | Hard| BFS
+|116|[Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)|[Solution](../../blob/master/MEDIUM/src/medium/PopulatingNextRightPointersinEachNode.java)| O(n)|O(1) | Medium| BFS
 |91|[Decode Ways](https://leetcode.com/problems/decode-ways/)|[Solution](../../blob/master/MEDIUM/src/medium/DecodeWays.java)| O(n)|O(n) | Medium| DP
 |76|[Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)|[Solution](../../blob/master/HARD/src/hard/MinimumWindowSubstring.java)|O(n)|O(k)|Hard|Two Pointers
 |56|[Merge Intervals](https://leetcode.com/problems/merge-intervals/)|[Solution](../../blob/master/HARD/src/hard/MergeIntervals.java)|O(n*logn)|O(1)|Hard|
