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

/**
 * // 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 queue = [root];
  let cur = root;
  while (queue.length) {
    const newQueue = [];
    let prevNode = null;
    while (queue.length) {
      const node = queue.pop();
      if (prevNode) {
        prevNode.next = node;
      }
      prevNode = node;
      if (node.left) {
        newQueue.unshift(node.left);
      }
      if (node.right) {
        newQueue.unshift(node.right);
      }
    }
    if (newQueue.length) {
      queue = newQueue;
    }
  }
  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) {
  // 如果为空的话就返回null
  if (!root) return null;
  let leftMost = root;
  while (leftMost.left) {
    let head = leftMost;
    while (head) {
      // head.left一定存在，head.right也存在，因为是完美二叉树
      // 连接左右
      head.left.next = head.right;
      if (head.next) {
        head.right.next = head.next.left;
      }
      head = head.next;
    }
    leftMost = leftMost.left;
  }
  return root;
};