116 Populating Next Right Pointers in Each Node

题目

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

The number of nodes in the given tree is less than 4096.
-1000 <= node.val <= 1000

解题思路

1 因为是完美二叉树,因此所有节点(不包括叶子节点)都一定有两个子节点.
广度优先遍历二叉树,将同一层的所有节点储存在数组中.
对于数组中的节点 n (下标为 i), 如果存在 n1 (下标为 i + 1), 则 n1 一定是 n 的右侧节点.

代码实现

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}
 */
function connect(root) {
  if (!root) {
    return root;
  }
    // 广度优先遍历
  // 当前层的节点
  let currentLevelNodes = [root];
  // 下一层的所有子节点
  let nextLevelNodes = [];
  while (currentLevelNodes.length) {
    const len = currentLevelNodes.length;
    for (let i = 0; i < len; i++) {
      const node = currentLevelNodes[i];
      // 获取右侧节点
      node.next = (i + 1 < len) ? currentLevelNodes[i + 1] : null;
      if (node.left) {
        nextLevelNodes.push(node.left);
      }
      if (node.right) {
        nextLevelNodes.push(node.right);
      }
    }
    currentLevelNodes = nextLevelNodes;
    nextLevelNodes = [];
  }
  return root;
};


// test
function createTree(val = 1, deep = 2) {
  if (deep < 0) {
    return null;
  }
  const node = new Node(val);
  node.left = createTree(val * 2, deep - 1);
  node.right = createTree(val * 2 + 1, deep - 1);
  return node;
}

const root = createTree(1);
console.log(JSON.stringify(root, '\n', 2));

2 观察完美二叉树的结构可知:

• 左子树的右侧节点一定是右子树
• 右子树的右侧节点(node.right.next)一定是其父节点的右侧节点的左子树(node.next.left)

因此可以通过父节点来获取对应的右侧节点.

代码实现
1 循环

function connect(root) {
  if (!root) {
    return root;
  }
  // 当前层最左侧的节点
  let leftmostNode = root;
  while (leftmostNode.left) {
    let node = leftmostNode;
    while (node) {
      // 左子节点右侧节点一定是父节点的右子节点
      node.left.next = node.right;
      if (node.next) {
       // 右子节点的右侧节点一定是父节点的右侧节点的左节点
        node.right.next = node.next.left;
      }
      // 储存右侧节点
      node = node.next;
    }
    // 储存下一层的最左侧节点
    leftmostNode = leftmostNode.left;
  }
  return root;
};

2 递归

function connect(root) {
  function dfs(node, next) {
    if (!node) {
      return null;
    }
    node.next = next;
    dfs(node.left, node.right);
    dfs(node.right, node.next ? node.next.left: null);
  }
  dfs(root, null);
  return root;
};