面试150 填充每个节点的下一个右侧节点指针Ⅱ

思路

采用层序遍历的方式来连接二叉树中同一层的节点。首先将根节点加入队列，然后按层处理节点：每一层依次从队列中取出节点，并将其 next 指针指向该层中的下一个节点（即队列中的下一个节点）；若是该层最后一个节点，则不进行连接。遍历过程中，如果当前节点存在左右子节点，则将其加入队列以供下一层处理。最终返回连接完毕的根节点。

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution:def connect(self, root: 'Node') -> 'Node':#层序遍历queue=deque()if root:queue.append(root)result=[]while queue:L=len(queue)while L:L-=1node=queue.popleft()if L>0:node.next=queue[0]if node.left:queue.append(node.left)if node.right:queue.append(node.right)  return root