type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。
二叉树的节点如下:
填充它的每个
next指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将
next指针设置为NULL。初始状态下,所有
next指针都被设置为NULL。示例 1:

示例 2:
解法一:BFS
用广度优先搜索(BFS)一层一层地访问节点,然后把同一层的节点用 next 串起来:
- 用队列(queue)存放每一层的节点;
- 每次循环时,我们把当前层的所有节点弹出,依次相连;
- 同时把它们的左右孩子放入队列,以便处理下一层。
复杂度
- 时间:O(N) 每个节点都恰好进出队列一次。
- 空间:O(N) 队列最多存放一层节点(最后一层有 N/2 个)。
解法二:迭代(推荐)
我们可以不用额外的队列,而是直接利用已经建立好的
next 链接来遍历每一层。- 当处理第N层节点时,第N层的
next已经连接好了(或即将被连接),
我们就能用它来为第 N+1 层的节点建立连接。
- 对于每个节点
node: - 连接它的左、右孩子:
node.left.next = node.right - 如果
node还有右邻居(即node.next存在),还需要让node.right.next = node.next.left
- 然后向下走到下一层,重复操作。
相当于逐层扫描链表,通过上一层的
next链条,构建下一层的next链条。因为是完美二叉树,不用担心空指针问题。
复杂度
- 时间:O(N) 每个节点只被访问一次。
- 空间:O(1) 我们只用了几个指针,没有额外结构。
解法三:递归
和解法二的思路一样,用递归写。
- 当前节点:
- 连接左右子节点;
- 如果它有
next,让它的右孩子和右邻节点的左孩子相连;
- 然后递归地处理左右子树。
复杂度
- 时间:O(N) 每个节点访问一次。
- 空间:O(N)(递归栈空间)。
解法四:BFS + prev 指针
这是另一种 BFS 实现方式,等价于解法一,只是显式维护一个
prev 指针去连接。复杂度
- 时间:O(N) 每个节点都恰好进出队列一次。
- 空间:O(N) 队列最多存放一层节点(最后一层有 N/2 个)。
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-116-填充每个节点的下一个右侧节点指针
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 105] 从前序与中序遍历序列构造二叉树
下一篇
[Leetcode 121] 买卖股票的最佳时机