Lt116. 填充每个节点的下一个右侧节点指针、dfs、队列、递归

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

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有  next 指针都被设置为 NULL。
 示例：

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

思路

非常数空间-队列实现

按不符合提议的非常数空间，可以有一种很简单的实现方式，队列层次遍历，只需要借用一个记录前一个节点地址的变量，每次遍历将上一个节点的 next 设为当前节点即可。

递归-dfs

参考「手画图解」DFS 递归 | 易于理解

如图所示，只有两种情况需要处理：

1. 该节点存在 next，为左孩子，如 2，将左孩子的 next 指向右孩子，还需要将右孩子的 next 指向当前节点 next 的左孩子
2. 该节点不存在 next，为 root 或右孩子，如 1，3，将左孩子的 next 指向右孩子

当为叶子节点，不存在左右孩子时跳出递归

最左指针-dfs

和上一个方法类似，使用一个最左指针，指向每一层的最左边的节点，之后进行每层层次遍历，处理逻辑基本同上：

1. 当前节点存在 next，为左孩子，如 2，将左孩子的 next 指向右孩子，还需要将右孩子的 next 指向当前节点 next 的左孩子
2. 当前节点不存在 next，为 root 或右孩子，如 1，3，将左孩子的 next 指向右孩子
3. 遍历该层下一个节点，指向该节点的 next

解答

非常数空间-队列实现

/**
 * // 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 = [];
  queue.push(root);
  while (queue.length) {
    let temp = queue.splice(0, queue.length);
    let pre = null;
    while (temp.length) {
      const node = temp.shift();
      if (pre) pre.next = node;
      pre = node;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return root;
};

递归-dfs

/**
 * // 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 dfs = (root) => {
    if (!root.left && !root.right) return;
    root.left.next = root.right;
    if (root.next) root.right.next = root.next.left;
    dfs(root.left);
    dfs(root.right);
  };
  dfs(root);
  return root;
};

最左指针-dfs

/**
 * // 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 leftMost = root;
  while (leftMost.left) {
    let temp = leftMost;
    while (temp) {
      temp.left.next = temp.right;
      if (temp.next) temp.right.next = temp.next.left;
      temp = temp.next;
    }
    leftMost = leftMost.left;
  }
  return root;
};