【一天一大 lee】填充每个节点的下一个右侧节点指针 II (难度:中等) - Day20200928

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

/**
 * // 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 == null) return null
  let queue = [root]
  while (queue.length) {
    let len = queue.length,
      last = null
    for (let i = 1; i <= len; ++i) {
      let node = queue.shift()
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
      if (i !== 1) last.next = node
      last = node
    }
  }
  return root
}

var connect = function(root) {
  if (root == null) return null
  let start = root, // 上一层构建next的触发点
    nextStart = null, // 下一轮构建next的触发点
    perv = null // 上一轮后构建的节点

  while (start) {
    // 开启新一层时 上一轮后构建的节点修改为null
    perv = null
    nextStart = null
    // 遍历的指针在同层节点中通过 next 连接（在遍历重来中构建了next，开启下次遍历时使用构建的next改变指针）
    for (let p = start; p; p = p.next) {
      // 先构建left，刷新perv 再构建right
      if (p.left) helper(p.left)
      if (p.right) helper(p.right)
    }
    // 更新触发点
    start = nextStart
  }

  function helper(p) {
    if (perv) perv.next = p
    if (nextStart == null) nextStart = p
    perv = p
  }
  return root
}