134 lines
4.0 KiB
JavaScript
134 lines
4.0 KiB
JavaScript
/**
|
||
* // Definition for a _Node.
|
||
* function _Node(val, left, right, next) {
|
||
* this.val = val === undefined ? null : val;
|
||
* this.left = left === undefined ? null : left;
|
||
* this.right = right === undefined ? null : right;
|
||
* this.next = next === undefined ? null : next;
|
||
* };
|
||
*/
|
||
|
||
/**
|
||
* @param {_Node} root
|
||
* @return {_Node}
|
||
*/
|
||
const connect = function (root) {
|
||
|
||
};
|
||
|
||
/*
|
||
按照题目的意思，很容易想到层序遍历，利用BFS拿到每一层的所有元素，定义一个last变量表示需要
|
||
设置next的节点，默认为当前层的第一个，之后遍历后面的所有元素，last.next = node，即可，node.next
|
||
默认为null，所以不要考虑为最后一个节点设置next
|
||
*/
|
||
|
||
function f1(root) {
|
||
if (!root) return root;
|
||
|
||
const queue = [root]; // 定义队列，用于层序遍历
|
||
|
||
while (queue.length) {
|
||
// 获取当前层的节点个数，用于遍历设置next
|
||
let n = queue.length;
|
||
// 定义last用于设置next
|
||
let last = null;
|
||
for (let i = 0; i < n; i++) {
|
||
const node = queue.shift();
|
||
|
||
if (node.left) queue.push(node.left);
|
||
if (node.right) queue.push(node.right);
|
||
|
||
// 如果不是第一个node
|
||
if (i !== 0) {
|
||
last.next = node;
|
||
}
|
||
last = node;
|
||
}
|
||
n = queue.length;
|
||
}
|
||
|
||
return root;
|
||
}
|
||
|
||
/*
|
||
利用栈来储存每一层的节点再获取下一层的节点有点浪费空间，因为原本就已经有一个next
|
||
来指向下一层的节点了，我们可以利用这个特点来遍历每一层的节点，并且为它下一层的节点
|
||
建立next指针，直到下一层没有节点，这样所有的节点就都构建好next指针
|
||
*/
|
||
|
||
function f2(root) {
|
||
if (!root) return root; // 如果根节点为空，直接返回
|
||
|
||
let nextStart = root; // 初始时为根节点
|
||
|
||
// 1. 每一层的遍历，直到没有更多节点
|
||
while (nextStart) {
|
||
let last = null; // 记录每一层的最后一个节点，用来连接
|
||
let cur = nextStart; // 当前层的遍历指针
|
||
nextStart = null; // 下一层的起始节点初始化为空
|
||
|
||
// 2. 遍历当前层的节点
|
||
while (cur) {
|
||
// 3. 如果当前节点有左子节点
|
||
if (cur.left) {
|
||
// 如果last不为空，说明上一个节点已连接，需要更新next
|
||
if (last) last.next = cur.left;
|
||
last = cur.left; // 更新last为当前左子节点
|
||
// 如果nextStart为空，表示当前左子节点是下一层的第一个节点
|
||
if (!nextStart) nextStart = cur.left;
|
||
}
|
||
|
||
// 如果当前节点有右子节点
|
||
if (cur.right) {
|
||
if (last) last.next = cur.right;
|
||
last = cur.right; // 更新last为当前右子节点
|
||
// 如果nextStart为空，表示当前右子节点是下一层的第一个节点
|
||
if (!nextStart) nextStart = cur.right;
|
||
}
|
||
|
||
// 移动到当前节点的下一个节点
|
||
cur = cur.next;
|
||
}
|
||
}
|
||
|
||
// 返回根节点，确保修改后的树结构被返回
|
||
return root;
|
||
}
|
||
|
||
/*
|
||
思路和f2一致，但是通过递归处理
|
||
*/
|
||
function f3(node) {
|
||
if (!node) return; // 如果节点为空，直接返回
|
||
|
||
let nextStart = null; // 用来记录下一层的第一个节点
|
||
let last = null; // 用来记录当前层最后一个节点
|
||
|
||
// 遍历当前层的所有节点
|
||
while (node) {
|
||
// 连接左子节点
|
||
if (node.left) {
|
||
if (last) {
|
||
last.next = node.left; // 连接当前节点的上一个节点的next
|
||
}
|
||
last = node.left; // 更新last为当前左子节点
|
||
if (!nextStart) nextStart = node.left; // 如果nextStart为空，设置为当前左子节点
|
||
}
|
||
|
||
// 连接右子节点
|
||
if (node.right) {
|
||
if (last) {
|
||
last.next = node.right; // 连接当前节点的上一个节点的next
|
||
}
|
||
last = node.right; // 更新last为当前右子节点
|
||
if (!nextStart) nextStart = node.right; // 如果nextStart为空，设置为当前右子节点
|
||
}
|
||
|
||
node = node.next; // 移动到当前节点的下一个节点
|
||
}
|
||
|
||
// 递归处理下一层
|
||
f3(nextStart);
|
||
return node;
|
||
}
|