@@ -0,0 +1,2177 @@
+/***%0A * Follow up for problem %22Populating Next Right Pointers in Each Node%22.%0A *%0A * What if the given tree could be any binary tree? Would your previous solution still work?%0A *%0A * Note:%0A *%0A * You may only use constant extra space.%0A * For example,%0A * Given the following binary tree,%0A *          1%0A *         /  %5C%0A *        2    3%0A *       / %5C    %5C%0A *      4   5    7%0A * After calling your function, the tree should look like:%0A *          1 -%3E NULL%0A *         /  %5C%0A *        2 -%3E 3 -%3E NULL%0A *       / %5C    %5C%0A *      4-%3E 5 -%3E 7 -%3E NULL%0A */%0A/**%0A * Definition for binary tree with next pointer.%0A * public class TreeLinkNode %7B%0A *     int val;%0A *     TreeLinkNode left, right, next;%0A *     TreeLinkNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Apublic class PopulatingNextRightPointersinEachNodeII %7B%0A    // Solution 1: O(n) O(1)%0A    public void connect(TreeLinkNode root) %7B%0A        if (root == null) return;%0A%0A        TreeLinkNode dummy = new TreeLinkNode(0);%0A        for (TreeLinkNode cur = root, prev = dummy;%0A                cur != null; cur = cur.next) %7B%0A            if (cur.left != null) %7B%0A                prev.next = cur.left;%0A                prev = prev.next;%0A            %7D%0A            if (cur.right != null) %7B%0A                prev.next = cur.right;%0A                prev = prev.next;%0A            %7D%0A        %7D%0A        connect(dummy.next);%0A    %7D%0A%0A    // Solution 2: O(n) O(1)%0A    public void connect(TreeLinkNode root) %7B%0A        while (root != null) %7B%0A            TreeLinkNode next = null; // The first node of next level%0A            TreeLinkNode prev = null; // Previous node on same level%0A            for (; root != null; root = root.next) %7B%0A                if (next == null)%0A                    next = root.left != null? root.left : root.right;%0A                if (root.left != null) %7B%0A                    if (prev != null)%0A                        prev.next = root.left;%0A                    prev = root.left;%0A                %7D%0A                if (root.right != null) %7B%0A                    if (prev != null)%0A                        prev.next = root.right;%0A                    prev = root.right;%0A                %7D%0A            %7D%0A            root = next; // turn to next level%0A        %7D%0A    %7D%0A%7D%0A

add PopulatingNextRightPointersinEachNodeII.java