117. 填充每个节点的下一个右侧节点指针 II
题目
给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输出：[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 进队列，继续循环。
按照以上的思路，就有如下代码：
function connect(root: Node | null): Node | null {
if (!root) return null;
const queue = [root]
while (queue.length) {
const node: Node = queue.shift() as Node;
if (!(node.left || node.right)) continue
if (node.left && node.right) node.left.next = node.right
const start = node.right || node.left as Node
const end = node.next ? (node.next.left || node.next.right) : null
start.next = end
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
return root
};提交后，有 34 / 55 个通过的测试用例，而失败的是这个用例：[1,2,3,4,5,null,6,7,null,null,null,null,8]
node.next，没有考虑node.next没有孩子而node.next.next有孩子的情况，造成了最后一行没有连起来。
加上判断后，代码顺利通过～
function connect(root: Node | null): Node | null {
if (!root) return null;
const queue = [root]
while (queue.length) {
const node: Node = queue.shift() as Node;
if (!(node.left || node.right)) continue
if (node.left && node.right) node.left.next = node.right
const start = node.right || node.left as Node
let nextWithChild = node.next
while (nextWithChild) {
if (nextWithChild.left || nextWithChild.right) break
nextWithChild = nextWithChild.next
}
const end = nextWithChild ? (nextWithChild.left || nextWithChild.right) : null
start.next = end
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
return root
};