https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

难度：中等

---

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

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

  填充它的每个 next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next指针设置为 NULL。

  初始状态下，所有 next指针都被设置为 NULL。

示例：

---

  首先，给定的树是一棵完美二叉树，因此对于所有非叶子节点的节点，都会有左右孩子。

解法1：层次优先遍历

  由于每个节点的 next 指针都是指向当前层次的右边节点，因此很容易想到使用层次优先遍历，且由于是完美二叉树，每层的节点个数也很容易计算出来（即都是 2 的倍数）。

  具体做法是使用一个队列，从右到左往队列中添加节点，这样，除了最右侧节点，其他节点在出队时将其 next 指向上一个出队节点即可。

JS 代码如下：

/**
 * // 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 = [];
    let last, cur;
    let n = 0, nums = 1;

    queue.push(root);

    while (queue.length) {
        cur = queue.shift();
        n++;
        if (last) {
            cur.next = last;
        }

        if (cur.right) {
            queue.push(cur.right);
        }
        if (cur.left) {
            queue.push(cur.left);
        }

        last = cur;
        if (n === nums) {
            nums *= 2;
            n = 0;
            last = null;
        }
    }

    return root;
};

解法2：使用父节点 next 指针

  首先，如下图，对于当前遍历到的节点 2，我们能够很容易的找到其左孩子的 next 指针所指向的节点（即其右孩子）：root.left.next = root.right;

  而对于其右孩子 5，由于我们在遍历根结点 1 时就设置了节点 2 的 next 指针，因此我们能够使用节点 2 的 next 来找到节点 5 的 next 所要指向的右侧节点：root.right.next = root.next.left;

  根据这种思路，我们能够写出递归版本和迭代版本的代码：

递归

  递归版本很直观，就是按照上面的两种情况来的：

var connect = function(root) {
    if (!root) {
        return root;
    }
    
    const dfs = (root) => {
        if (!root) {
            return;
        }

        if (root.left) {
            root.left.next = root.right;
			// 若当前节点不是最右侧节点，那么可以通过 next 指针找到其右侧节点
            if (root.next) {
                root.right.next = root.next.left;
            }
        }

        dfs(root.left);
        dfs(root.right);
    };

    dfs(root);

    return root;
};

迭代

  对于迭代法，我们可以从每一层最左边的节点出发，对每一个遍历到的节点的左右孩子，按照上面的两种情况来获取 next 的指向：

var connect = function(root) {
    if (!root) {
        return root;
    }
    
    let leftSide = root;
    while (leftSide.left) {
        let node = leftSide;
        while (node) {
            node.left.next = node.right;
            if (node.next) {
                node.right.next = node.next.left;
            }
            node = node.next;
        }
        leftSide = leftSide.left;
    }

    return root;
};