Code & Func
2020-10-12

今天的题目是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的时候,如果nnext指针已经确定了,我们就可以通过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
}
上一条动态