LeetCode题练习与总结：填充每个节点的下一个右侧节点指针Ⅱ--117

一、题目描述

给定一个二叉树：

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

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

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

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

输入：root = []
输出：[]

提示：

树中的节点数在范围 [0, 6000] 内
-100 <= Node.val <= 100

二、解题思路

这个问题是一个典型的二叉树的层序遍历问题，但与其打印每层的节点值，我们需要设置每层节点的 next 指针。我们可以使用一个队列来实现层序遍历，并在每层遍历结束后更新每个节点的 next 指针。

解题思路如下：

1. 如果根节点为空，直接返回 null。

2. 初始化一个队列，并将根节点入队。

3. 当队列不为空时，进行以下操作：

获取当前队列的大小，这个大小即为这一层的节点数。
遍历这一层的节点：
- 出队当前节点。
- 如果当前节点有左子节点，将左子节点入队。
- 如果当前节点有右子节点，将右子节点入队。
- 如果当前节点不是这一层的最后一个节点，将当前节点的 next 指针指向队列中下一个节点（即将出队的节点）。

4. 继续步骤3，直到队列为空。

三、具体代码

import java.util.LinkedList;
import java.util.Queue;class Solution {public Node connect(Node root) {if (root == null) {return null;}Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {Node node = queue.poll();if (i < levelSize - 1) {node.next = queue.peek();}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return root;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

每个节点都会被访问一次，因为我们需要为每个节点设置 next 指针。
在层序遍历中，每个节点都会被加入队列一次，并且也会从队列中移除一次。
因此，时间复杂度主要取决于树的节点数，记为 N。
对于每个节点，我们在队列中的操作是常数时间的，即 O(1)。
所以，总的时间复杂度是 O(N)。

2. 空间复杂度

空间复杂度主要取决于队列中存储的最大节点数，这通常发生在树的最后一层。
在最坏的情况下，树是完全二叉树，最后一层的节点数是前面所有层节点数之和再加1，即 2^(h-1)，其中 h 是树的高度。
因此，空间复杂度是 O(2^(h-1))，这可以简化为 O(N)，因为在完全二叉树中，h 大约是 log(N)，所以 2^(h-1) 是 N/2，这是线性的。
在实际情况中，如果树不是完全二叉树，队列中同时存在的节点数可能会更少，但这不会影响空间复杂度的阶数，它仍然是 O(N)。

综上所述，给定代码的时间复杂度是 O(N)，空间复杂度也是 O(N)。

五、总结知识点

二叉树结构：代码操作的是一种特殊的二叉树结构，其中每个节点除了左右子节点的指针外，还有一个指向下一个节点的指针。
层序遍历（广度优先搜索）：代码使用了队列来实现二叉树的层序遍历，这是一种广度优先搜索的应用。层序遍历按照树的层级顺序访问节点，通常用于解决与层级相关的树的问题。
队列的使用：代码中使用了一个 LinkedList 实现的 Queue 来存储每一层的节点。队列是一种先进先出（FIFO）的数据结构，在这里用于按顺序访问每一层的节点。
迭代与循环：代码中使用了一个 while 循环来迭代处理每一层的节点，直到队列为空，即所有节点都被访问过。
节点关系的建立：在层序遍历的过程中，代码为每个节点建立了 next 指针，指向其在同一层中的下一个节点。这是通过队列的 peek 方法实现的，它允许我们查看队列的头部元素而不移除它。
边界条件处理：代码首先检查了根节点是否为空，这是对输入数据的有效性检查，确保了代码的鲁棒性。
节点入队：在遍历过程中，代码将每个节点的非空子节点加入队列，为下一层的遍历做准备。
链表操作：虽然代码操作的是二叉树，但在每一层中，节点的 next 指针形成了一个链表。代码中的 node.next = queue.peek(); 操作实际上是在链表中建立节点之间的关系。
常数时间操作：代码中对于每个节点的处理是常数时间的，这是因为队列的入队和出队操作都是 O(1)。
递归与迭代的选择：虽然二叉树的问题通常可以用递归方法解决，但这里选择了迭代方法，使用队列来实现层序遍历。递归和迭代是解决树相关问题的两种常见方法。