116. Populating Next Right Pointers in Each Node

LeetCode
, ,

今天的题目是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的时候，如果n的next指针已经确定了，我们就可以通过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;
}