116.+117. 填充每个节点的下一个右侧节点指针（Ⅰ+Ⅱ）（中）

• 题目
• 题解：BFS

题目

• 给定一个 完美二叉树 （117的Ⅱ题不是完美二叉树，是二叉树，其余一样），其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

题解：BFS

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        #BFS遍历每一层的时候，队列头指向队尾，队尾元素指向空
        if not root:#如果根节点为空
            return None
        q=[root]#用列表做队列
        while q:
            size=len(q)
 
            for i in range (size):
                cur=q.pop(0)#弹出队头元素
                if i < size - 1:#当元素不是这一层的最后一个时
                    next_node = q[0]#存储下一个节点
                    cur.next=next_node#把当前节点的next指向下一个节点
                else:#当元素是这一层的最后一个时，指向空
                    cur.next=None
                if cur.left:#有左孩子加入队列
                    q.append(cur.left)
                if cur.right:#有右孩子加入队列
                    q.append(cur.right)
        return root#返回根节点