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

思路：
说实话没读明白这个题 题目描述十分微妙 该题显然也是层次遍历 需要注意的是需要用一个node将所有节点串起来，这里用了一个虚拟头，让我想起来了删除链表的美好时光。加油！~~

"""
# 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':
if not root:
return root
# q = collections.deque() # 队列
# q.append(root) # 根节点入队
q = [root]
while q:
temp = Node() # 用于保存同层的前一个节点,初始为虚拟头节点
size = len(q) # 当前层节点的个数(不包括最左边第一个)
for _ in range(size):
cur = q.pop(0) # 当前出队元素
temp.next = cur # 让同层左边一个元素作为当前元素
if cur.left: q.append(cur.left) # 左子树入队
if cur.right: q.append(cur.right) # 右子树入队
temp = cur # 更新前一个节点为当前节点

return root