117. Populating Next Right Pointers in Each Node II

# Medium

Very similar to #116, but the tree is not balance tree.

Two methods:

1. Recursive, very complex, have to find the most left child of the parent node

2. no-recursive, easy, same as #116

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
                # stop condition
        if root == None:
            return None
        
        # regular case
        tmp = root.next   # 找到与父节点平行的下一个节点（父‘）
        while tmp != None:
            if tmp.left != None:
                tmp = tmp.left
                break
            if tmp.right != None:
                tmp = tmp.right
                break
            tmp = tmp.next  # 找到（父’）最左边的子节点
        
        if root.left != None:  # 父节点的左子树存在
            if root.right != None:   # 父节点右子树存在，则左->右->离其最近的节点tmp
                root.left.next = root.right
                root.right.next = tmp
            else:  # 父节点右子树不存在，则左->离其最近的节点tmp
                root.left.next = tmp
        else:  # 父节点左子树不存在
            if root.right != None:   # 父节点右子树存在，则右->离其最近的节点tmp
                root.right.next = tmp
                
        
        self.connect(root.right)  # can't switch the connect order
        self.connect(root.left)   # 因为连完了右边的才能连起来左边？？？
        
        return root