116. Populating Next Right Pointers in Each Node

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

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

代码如下:

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

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

代码如下:

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

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

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

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