题目
- 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
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#返回根节点