Populating Next Right Pointers in Each Node

Description

doc

Solutions

First Idea

/**
 * // 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}
 */
var connect = function (root) {
  if (!root) {
    return root
  }

  let queue = [root]
  let nextQueue = []
  let prev = null

  while (queue.length) {
    const tail = queue.shift()
    tail.next = prev
    prev = tail

    tail.right && nextQueue.push(tail.right)
    tail.left && nextQueue.push(tail.left)

    if (queue.length === 0) {
      queue = nextQueue
      nextQueue = []
      prev = null
    }
  }

  return root
}