LeetCode 116 [Populating Next Right Pointers in Each Node]

题目链接

题目描述

  • 给定一颗完美二叉树,要求将每个结点的next指针指向它右侧的结点,若它右侧没有结点,则指向NULL,处理过程只能使用常量复杂度的空间。

解题思路

  • 对于任意两个在完美二叉树上左右相邻的结点,它们必定满足以下两个规则之一:
    • 它们有同一个父结点,即任意一个结点的左右子结点必然是相邻的
    • 两个结点的父结点相邻,并且位于左侧的结点是它的父结点的右子结点,位于右侧的结点是它的父结点的左子结点
  • 既然确定了左右相邻的结点的特征,那么只需要从根结点开始遍历树的所有结点并对应处理即可,处理过程如下:
    1. 对于每个结点,若左子结点存在,那么右子结点也必然存在,则将左子结点的next指针指向右子结点
    2. 对于每个结点,若它的左子结点也存在右子结点,那么它的右子结点也存在左子结点,则将它的左子结点的右子结点的next指针,指向它的右子结点的左子结点
  • 处理过程中,每个结点都被遍历了一次,因此时间复杂度是O(n)

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) return;
if (root->next && root->right) root->right->next = root->next->left;
if (root->left) {
root->left->next = root->right;
connect(root->left);
connect(root->right);
}
}
};