"""
# 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