74.填充每个节点的下一个右侧节点指针 II
题目
给定一个二叉树：
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
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
思路
如果第N层的next已经连好了，我就能像遍历链表一样走完第N层，顺便把第N+1层也连好。
思路一: BFS层序遍历(最直观)
用队列做层序遍历，每层处理时把相邻节点连起来。
class Solution {
fun connect(root: Node?): Node? {
if (root == null) return null
val queue = ArrayDeque<Node>()
queue.add(root)
while (queue.isNotEmpty()) {
val size = queue.size // 当前层的节点数
for (i in 0 until size) {
val node = queue.removeFirst()
// 不是本层最后一个节点，就连上下一个
if (i < size - 1) {
node.next = queue.first()
}
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
}
return root
}
}
时间复杂度: O(n)
缺点：用了 O(n) 的队列空间，题目进阶要求 O(1) 空间。
思路二:利用已建好的next指针(O(1)空间)
核心思路: 在当前层next已经建好，就可以像链表一样遍历当前层，同时为下一层简历next链接。
- curr: 当前层的遍历指针，像你在当前排走动
- dummy: 哨兵，站在下一排的最坐标，作为起点，减少对起点的异常边界判断
- tail: 下一排的最后一个，初始时就是dummy
class Solution {
fun connect(root: Node?): Node? {
var curr = root // 从根节点开始，逐层往下
while (curr != null) {
// 每处理一层，都给下一层准备一个虚拟头节点
val dummy = Node(0)
var tail = dummy // tail 是下一层链表的末尾，初始指向 dummy
// 遍历当前层（因为上一轮已经连好了 next，所以可以直接用 next 遍历）
while (curr != null) {
if (curr.left != null) {
tail.next = curr.left // 把左孩子接到下一层链表末尾
tail = tail.next!! // tail 向后移
}
if (curr.right != null) {
tail.next = curr.right // 把右孩子接到下一层链表末尾
tail = tail.next!! // tail 向后移
}
curr = curr.next // 当前层向右走
}
// 当前层处理完毕，下移到下一层的第一个节点
curr = dummy.next
}
return root
}
}
复杂度
- 时间复杂度: O(n)，每个节点只访问一次
- 空间复杂度: 只用了dummy和tail两个额外的指针，没有队列
- 邮箱 ：charon.chui@gmail.com
- Good Luck!