116. 填充每个节点的下一个右侧节点指针

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

解法一：层序

对每层结点，前后连接起来即可

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left, right, next):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        queue = [root]
        while queue:
            last = None     #记录同一层前一个结点，初始为空
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                if last:
                    last.next = node
                last = node
        return root

解法二：递归

前序遍历（后序也可以）

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:  #出口
            return
        #若有左子，则也有右子（满二叉树）
        if root.left:
            root.left.next = root.right  #左连接右
            #右子连接父亲兄弟结点的左子（若存在）
            root.right.next = root.next.left if root.next else None 
        #递归左右子树（前序）
        self.connect(root.left)
        self.connect(root.right)
        return root

也可以到叶节点就返回，不用每次都递归到空节点

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:  #出口
            return
        if not root.left:    #叶节点直接返回（若有左子，则也有右子（满二叉树）
            return root
        root.left.next = root.right  #左连接右
        #右子连接父亲兄弟结点的左子（若存在）
        root.right.next = root.next.left if root.next else None 
        #递归左右子树（前序
        self.connect(root.left)
        self.connect(root.right)
        return root