填充每个节点的下一个右侧节点指针 II
给定一个二叉树：
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
示例 1：
codeType
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。 示例 2：
codeType
输入：root = []
输出：[]
提示：
- 树中的节点数在范围 [0, 6000] 内
- -100 <= Node.val <= 100
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。
解法
解法一：层序遍历
ts
/**
* Definition for _Node.
* class _Node {
* val: number
* left: _Node | null
* right: _Node | null
* next: _Node | null
*
* constructor(val?: number, left?: _Node, right?: _Node, next?: _Node) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function connect(root: _Node | null): _Node | null {
// 相当于进行一次层序遍历
if(!root) return root
let q = []
q.push(root)
while(q.length !== 0){
let n = q.length // 当前层的节点数
for(let i = 0; i < n; i++){
let curNode = q.shift()
if(i < n - 1){ // 除了每层的最后一个节点，都需要绑定next
curNode.next = q[0] // 要绑定的下个节点就是队首
}else{
curNode.next = null
}
if(curNode.left) q.push(curNode.left)
if(curNode.right) q.push(curNode.right)
}
}
return root
};
解法二：
利用已建立的next，想要建立第i层节点的next，只需要通过第i-1层的next就可以建立连接。从而实现O(1)的空间复杂度。
js
var connect = function(root) {
if (root === null) {
return null;
}
const queue = [root];
while (queue.length) {
const n = queue.length;
let last = null;
for (let i = 1; i <= n; ++i) {
let f = queue.shift();
if (f.left !== null) {
queue.push(f.left);
}
if (f.right !== null) {
queue.push(f.right);
}
if (i !== 1) {
last.next = f;
}
last = f;
}
}
return root;
};