116. Populating Next Right Pointers in Each Node

Oct 12, 2020

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

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

代码如下:

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指针。

代码如下:

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指针确定下来,而移动到下一层只需要记住树最左边节点的指针即可。

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;
}
LeetCodeTreeDepth-first SearchLeetCode

274. H-Index

1227. Airplane Seat Assignment Probability

comments powered by Disqus