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

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

思考

相同层级的操作可以想到的是层序遍,但是题目中有一个问题没有说清楚,下一个右侧节点表示紧邻的右侧节点,空节点也算是一个节点,换句话说空节点不能跳过

在思考一下其中的细节,需要清楚一层有多少个节点，这样才能准确遍历到一层的末尾, 链接的时候空的节点不能跳过，因为这也是合法的节点。

const connect = (root) => {
  if (root === null) return null;

  const queue = [root];
  while (queue.length) {
    // 记录每一层的长度
    let len = queue.length;

    while (len--) {
      const node = queue.shift();
      if (len && node) node.next = queue[0];

      // 不需要判断空节点
      if (node) queue.push(node.left, node.right);
    }
  }
  return root;
};

这个问题也可以用,递归来解决,因为它可以抽象成更小的子问题，也就是链接两个节点，需要知道的是哪些节点是需要链接的。

如果盲目的套用递归框架就会困惑，在另外一个子树的节点，怎么能获取到呢。

const connect = (root) => {
  if (root === null) return root;

  if (root.left) root.next = root.right;

  // 无法获取另外子树的节点

  return root;
};

所以需要指明，那两个节点需要链接，这也是一个先序遍历的模型，但是子问题需要传递更多的信息。

const dig = (left, right) => {
  // 链接两个节点
  if (left) left.next = right;
  if (left) dig(left.left, left.right);
  if (right) dig(right.left, right.right);
  // 不同子树中需要连接的节点
  if (left && right) dig(left.right, right.left);
};

const connect = (root) => {
  if (root === null) return root;
  dig(root.left, root.right);
  return root;
};

打赏