面试经典150题——填充每个节点的下一个右侧节点指针 II

​

1. 题目描述

2.  题目分析与解析

2.1 思路一

要解决填充每个节点的下一个右侧节点指针问题，我们可以使用层序遍历（也称广度优先遍历）的方法来实现。这种方法能够有效地处理每层节点，并按顺序连接它们的右侧指针。

1. 问题理解

这个问题要求我们将每个节点的 next 指针指向其右侧的节点。如果该节点是其层级中的最后一个节点，则其 next 指针应指向 null。问题的关键在于如何有效地访问并处理每层的节点，确保正确设置 next 指针。

2. 使用层序遍历

层序遍历是一种通过队列实现的遍历方法，它从根节点开始，逐层处理节点。在这个问题中，层序遍历特别适用，因为我们可以确保节点是按层级顺序处理的。

3. 实现层序遍历

• 初始化队列：首先将根节点放入队列中。这是遍历的起始点。

• 遍历队列：只要队列不为空，就继续处理。

• 处理当前层：在每一层的开始，我们获取当前队列的大小，这个大小表示当前层中的节点数量。然后，通过循环处理这些节点。

4. 连接节点

在处理每层的节点时，我们需要实现节点间的连接。

• 队列中的第一个节点：这个节点没有前一个节点可以连接，所以直接跳过设置 next 指针的步骤。

• 后续节点：从第二个节点开始，我们可以将前一个节点的 next 指针指向当前节点。

• 添加子节点：为了保证层序遍历可以进入下一层，我们需要将当前节点的左右子节点加入队列。

整体思路可以归纳为：

1. 创建一个队列，用于存储每一层的节点

2. 将根节点添加到队列中

3. 遍历队列

4. 根据队列的长度，遍历队列中的节点(当前层)并连接节点

2.2 优化

3. 代码实现

3.1 思路一

4. 相关复杂度分析

• 时间复杂度：O(N)，其中 N 是树中的节点数。每个节点都被处理一次。

• 空间复杂度：O(W)，其中 W 是树的最大宽度。这是因为队列最多需要存储一层的所有节点。

• 优化后的空间复杂度：O(1)。