117. 填充每个节点的下一个右侧节点指针 II

4 个月前
22

题目

给定一个二叉树:

填充它的每个 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 = [] 输出:[]

解答

我采用广度优先遍历,初始队列为[root],在拿到一个节点的情况下,进行分类讨论:

  1. 如果没有孩子:直接continue跳过
  2. 如果左右都有孩子,让左孩子的 next 指向右孩子
  3. 定义 start 作为上图 5->7 这种情况的起点,如果右存在则是右,否则是左孩子。
  4. 定义 end 为终点,如果该节点没有 next,则 end 为 null,否则是 next 的左孩子,否则是 next 的右孩子。
  5. 将孩子 push 进队列,继续循环。

按照以上的思路,就有如下代码:

提交后,有 34 / 55 个通过的测试用例,而失败的是这个用例:
[1,2,3,4,5,null,6,7,null,null,null,null,8]

画出这棵树的图可知,我们只考虑了node.next,没有考虑node.next没有孩子而node.next.next有孩子的情况,造成了最后一行没有连起来。

加上判断后,代码顺利通过~

评论区加载中...