[Leetcode 116] 填充每个节点的下一个右侧节点指针

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

解法一:BFS

广度优先搜索(BFS)一层一层地访问节点,然后把同一层的节点用 next 串起来:
  • 用队列(queue)存放每一层的节点;
  • 每次循环时,我们把当前层的所有节点弹出,依次相连;
  • 同时把它们的左右孩子放入队列,以便处理下一层。
复杂度
  • 时间:O(N) 每个节点都恰好进出队列一次。
  • 空间:O(N) 队列最多存放一层节点(最后一层有 N/2 个)。

解法二:迭代(推荐)

我们可以不用额外的队列,而是直接利用已经建立好的 next 链接来遍历每一层。
  1. 当处理第N层节点时,第N层的next已经连接好了(或即将被连接),
    1. 我们就能用它来为第 N+1 层的节点建立连接。
  1. 对于每个节点 node
      • 连接它的左、右孩子:node.left.next = node.right
      • 如果 node 还有右邻居(即 node.next 存在),还需要让 node.right.next = node.next.left
  1. 然后向下走到下一层,重复操作。
相当于逐层扫描链表,通过上一层的next链条,构建下一层的next链条。
因为是完美二叉树,不用担心空指针问题。
复杂度
  • 时间:O(N) 每个节点只被访问一次。
  • 空间:O(1) 我们只用了几个指针,没有额外结构。

解法三:递归

和解法二的思路一样,用递归写。
  • 当前节点:
    • 连接左右子节点;
    • 如果它有 next,让它的右孩子和右邻节点的左孩子相连;
  • 然后递归地处理左右子树。
复杂度
  • 时间:O(N) 每个节点访问一次。
  • 空间:O(N)(递归栈空间)。

解法四:BFS + prev 指针

这是另一种 BFS 实现方式,等价于解法一,只是显式维护一个 prev 指针去连接。
复杂度
  • 时间:O(N) 每个节点都恰好进出队列一次。
  • 空间:O(N) 队列最多存放一层节点(最后一层有 N/2 个)。
上一篇
[Leetcode 105] 从前序与中序遍历序列构造二叉树
下一篇
[Leetcode 121] 买卖股票的最佳时机