Code & Func

今天的题目是116. Populating Next Right Pointers in Each Node。

不算难的题目，因为题目中给出的树是特定的树，即所谓的完美二叉树，因此我们可以简单的用一个指针去获取左子树最右边的节点，右子树最左边的节点，然后直接对应相连。完成这一步后左子树和右子树之间已经通过next指针连接起来了，现在只需要递归地去连接左，右子树各自的next指针即可。

代码如下：

1
Node* connect(Node* root) {
2
  if (!root) return nullptr;
3
  Node* left = root->left;
4
  Node *right = root->right;
5
  while (left && right)
6
  {
7
    left->next = right;
8
    left = left->right;
9
    right = right->left;
10
  }
11
  connect(root->left);
12
  connect(root->right);
13
  return root;
14
}

上面的方法需要遍历多次节点，显然效率不是最高的，我们可以尝试利用上已经连接好的next指针，然后减少遍历节点的次数。在遍历到节点n的时候，如果n的next指针已经确定了，我们就可以通过next指针来访问到同一层相邻的节点，进而节点n的右孩子的next指针就可以在常数时间内找到，而节点n左孩子的next指针就是节点n的右孩子，所以在遍历到孩子节点前，我们就可以确定它们的next指针。

代码如下：

1
Node* connect(Node* root) {
2
  if (root && root->left) {
3
    root->left->next = root->right;
4
    root->right->next = root->next ? root->next->left : nullptr;
5
    connect(root->left);
6
    connect(root->right);
7
  }
8
  return root;
9
}

上面两种方法都是递归实现的，但是利用上next指针，我们可以实现一个没有额外空间的层次遍历。

连接的方式和第二种方法有点类似，只是遍历方式换掉了。这里是当访问到第i层时，该层所有节点的next指针都已经确定了。所以我们可以通过next指针来遍历这里层的所有节点，并用和第二种方法一样的方式将下一层节点的next指针确定下来，而移动到下一层只需要记住树最左边节点的指针即可。

1
Node* connect(Node *root) {
2
  Node* nextLayer = root;
3
  Node* p;
4
  while(nextLayer) {
5
    p = nextLayer;
6
    nextLayer = p->left;
7
    while (p && nextLayer)
8
    {
9
      p->left->next = p->right;
10
      p->right->next = p->next ? p->next->left : nullptr;
11
      p = p->next;
12
    }
13
  }
14
  return root;
15
}