广度优先遍历 BFS
解题思路
使用 层序遍历 进行遍历，队列里面会放置二叉树每一层的节点；
将队列的第一个元素与下一个元素连接起来；
复杂度
-
时间复杂度：
O(N)，每个节点会被访问一次且只会被访问一次，即从队列中弹出，并建立 next 指针； -
空间复杂度：
O(N)，这是一棵完美二叉树，它的最后一个层级包含 N/2 个节点，广度优先遍历的复杂度取决于一个层级上的最大元素数量，这种情况下空间复杂度为O(N)；
代码实现
var connect = function (root) {
if (root === null) return root;
const queue = [root]; // 初始化队列同时将第一层节点加入队列中，即根节点
// 外层的 while 循环迭代的是层数
while (queue.length > 0) {
// 记录当前队列大小
const len = queue.length;
// 遍历这一层的所有节点
for (let i = 0; i < len; i++) {
const node = queue.shift(); // 从队首取出元素
if (i < len - 1) node.next = queue[0]; // 连接
// 拓展下一层节点
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return root; // 返回根节点
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 116. 填充每个节点的下一个右侧节点指针
上一篇
评论
