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

/**
 * // 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 null;

  const queue = [root];
  while (queue.length > 0) {
    const n = queue.length;
    for (let i = 0; i < n; i++) {
      const node = queue.shift();
      if (i < n - 1) {
        node.next = queue[0];
      }

      if (node.left) {
        queue.push(node.left);
      }

      if (node.right) {
        queue.push(node.right);
      }
    }
  }
  return root;
};

/**
 * // 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 null;

  let nextStart = root;
  let last;
  const handle = (node) => {
    if (!node) return;
    if (!nextStart) {
      nextStart = node;
    }
    if (last) {
      last.next = node;
    }
    last = node;
  };

  while (nextStart) {
    let node = nextStart;
    nextStart = null;
    last = null;

    while (node) {
      handle(node.left);
      handle(node.right);
      node = node.next;
    }
  }

  return root;
};