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.

        1
       /  \
      2    3
     /      \
    4        7

Method 1 O(n) time, O(1) space.

• Go level by level, for each level we first remember its leftmost child.
• Use another child variable, set it initialize to the parent's left child first, then try set its right to the parent's left, it the parent's doesnt have a left child then dont set it.
• Move parent to parent's next, which means go right. Meanwhile, the child is still the previous parent's left child.

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        while root:
            child_copy = child = TreeLinkNode(0)
            while root:
                child.next = root.left
                child = child.next or child
                child.next = root.right
                child = child.next or child
                root = root.next
            root = child_copy.next