[Leetcode] Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

可以使用层次遍历的方法，但是空间复杂度为O(n)，为了达到O(1)，使用两个指针一个保存上一层的信息一个用来链接下一层的信息，因为上一层已经连接在一起，所以可以直接扫过去，然后我实现的思路是根据当前下一层节点与上一层节点的关系，来找到第一个合法的next，这样写比较冗长，一种比较好的思路是直接根据已经链接的节点来直接链接他们的孩子，注意在每次链接完一层，要找下一层的开始地方。

    public void connect(TreeLinkNode root) {
        if(root == null) return;
        root.next = null;
        TreeLinkNode parent = root;
        TreeLinkNode child = (root.left == null) ? (root.right) : (root.left);
        while(child != null) {
            TreeLinkNode temp1 = parent;
            TreeLinkNode temp2 = child;
            while(temp1 != null) {
                if(temp2 == temp1.left) {
                    if(temp1.right != null) {
                        temp2.next = temp1.right;
                        temp2 = temp2.next;
                    }
                    else {
                        temp1 = temp1.next;
                    }
                }
                else if(temp2 == temp1.right) {
                    temp1 = temp1.next;
                }
                else { // find next valid node with left or right child
                    while(temp1 != null && temp1.left == null && temp1.right == null) temp1 = temp1.next;
                    if(temp1 == null) temp2.next = null;
                    else if(temp1.left != null) {
                        temp2.next = temp1.left;
                        temp2 = temp2.next;
                    }
                    else {
                        temp2.next = temp1.right;
                        temp2 = temp2.next;
                    }
                }
            }
            temp1 = child; // find next level's start position
            while(temp1 != null && temp1.left == null && temp1.right == null) temp1 = temp1.next;
            if(temp1 == null) child = null;
            else {
                parent = temp1;
                child = (temp1.left == null) ? (temp1.right) : (temp1.left);
            }
        }
    }

    public void connect(TreeLinkNode root) {
        while(root != null) {
            TreeLinkNode next = null;
            TreeLinkNode pre = null;
            for(; root != null; root = root.next) {
                if(next == null) next = root.left == null ? root.right : root.left;
                if(root.left != null) {
                    if(pre != null) pre.next = root.left;
                    pre = root.left;
                }
                if(root.right != null) {
                    if(pre != null) pre.next = root.right;
                    pre = root.right;
                }
            }
            root = next;
        }
    }