算法每日一练:填充每个结点的下一个右侧结点指针 #代码

大家好，欢迎收看本期的算法每日一练。

本期的题目是填充每个节点的下一个右侧节点指针。

题目给定一个包含除左右指针外新增了那次指针的完全二叉树，该指针用来指向下一个右侧节点。如果没有右侧节点则需要指向空。

如下图中二指向三，四指向五，五指向六，六指向七。题目描述的下一个右侧节点其实就是要将兄弟节点建立指向关系。

这个题目需要使用二叉树的层次遍历逻辑去解释。

1. 先判断根是否为空，为空就直接返回空。

2. 再定义一个队列用来进行二叉树的层次辨别。

3. 接下来先将根进行入队，然后通过循环来对二叉树进行层次遍历。但是这里要做一些其他操作。

4. 在循环中定义一个整型变量来存储当前层的节点数量。

5. 然后需要再使用一个循环来将本层节点逐个出队，同时将下层节点入队。

6. 这里先获取本层的一个节点，然后将它出队。因为此时队列中的节点都是同一层的，所以只需要用当前节点的 next 指向队列中的第一个就可以了。但是需要考虑有可能队列中没有节点，所以这里进行了一下处理操作来防止队列中没有节点从而指向空。

7. 接下来就只需要和正常的层次遍历一样判断左右节点是否存在，存在就入队。循环的条件就是队列大小为零，把同一层的节点全部处理完。

8. 最后在最外层循环结束之后返回根就 ok。

来看看结果，还可以。

本期视频就到此结束，下期再见。