题目#

给定一个二叉树：

1
struct Node {
2
  int val;
3
  Node *left;
4
  Node *right;
5
  Node *next;
6
}

填充它的每个 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]，在拿到一个节点的情况下，进行分类讨论：

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

按照以上的思路，就有如下代码：

1
function connect(root: Node | null): Node | null {
2
  if (!root) return null;
3
  const queue = [root]
4
  while (queue.length) {
5
    const node: Node = queue.shift() as Node;
6
    if (!(node.left || node.right)) continue
7
    if (node.left && node.right) node.left.next = node.right
8
    const start = node.right || node.left as Node
9
    const end = node.next ? (node.next.left || node.next.right) : null
10
    start.next = end
11
    node.left && queue.push(node.left)
12
    node.right && queue.push(node.right)
13
  }
14
  return root
15
};

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

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

加上判断后，代码顺利通过～

1
function connect(root: Node | null): Node | null {
2
  if (!root) return null;
3
  const queue = [root]
4
  while (queue.length) {
5
    const node: Node = queue.shift() as Node;
6
    if (!(node.left || node.right)) continue
7
    if (node.left && node.right) node.left.next = node.right
8
    const start = node.right || node.left as Node
9
    let nextWithChild = node.next
10
    while (nextWithChild) {
11
      if (nextWithChild.left || nextWithChild.right) break
12
      nextWithChild = nextWithChild.next
13
    }
14
    const end = nextWithChild ? (nextWithChild.left || nextWithChild.right) : null
15
    start.next = end
16
    node.left && queue.push(node.left)
17
    node.right && queue.push(node.right)
18
  }
19
  return root
20
};