116.填充每个节点的下一个右侧节点指针

链接：116.填充每个节点的下一个右侧节点指针
难度：Medium
标签：树、深度优先搜索、广度优先搜索、链表、二叉树
简介：给定一个完美二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

题解 1 - typescript

• 编辑时间：2020-10-15
• 执行用时：108ms
• 内存消耗：45.3MB
• 编程语言：typescript
• 解法介绍：层序遍历。

function connect(root: Node | null): Node | null {
  if (root === null) return null;
  const queue = [root];
  let size = 1;
  while (queue.length !== 0) {
    const node = queue.shift()!;
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
    if (--size === 0) size = queue.length;
    else node.next = queue[0];
  }
  return root;
}