LeetCode 117 [Populating Next Right Pointers in Each Node II]

题目链接

题目描述

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

解题思路

  • 本题与题目116不一样的地方在于给定的二叉树是普通的,除了二叉树的基本特征之外,没有其他可以利用的特点
  • 若不限制使用的空间的复杂度,我们就可以通过遍历,把每一层最近一次被访问的结点记录下来,每次访问到同一层的下一个结点,就把记录的同层的结点的next指针指向当前结点,再把当前结点作为本层最近一次被访问的结点记录下来,这样遍历完之后next指针也就构建完毕了
  • 对于限制空间复杂度的条件,我们只能通过时间换空间的方式来解决。解决的方式是每一次遍历,目标仅针对特定某一层的结点,具体步骤如下:
    1. 假如根结点深度为0,叶结点最深的深度为h,在进行每一轮遍历之前,将辅助记录本层上一次访问的结点的指针置为NULL
    2. 进行一轮遍历时,从根结点开始,若当前结点的深度与本次遍历的目标层的深度一致,则对应更新next指针与辅助指针,对于深度超过目标的结点不需要遍历
    3. 每一轮遍历结束之后,若辅助指针不为NULL,说明需要继续下一轮遍历
    4. 经过h轮遍历之后,next指针即构建完毕
  • 假设二叉树高度为h,则处理过程对树遍历了h轮,设 0 < i <= h,则第i轮最多遍历 sum(2^0 + 2^1 + … + 2^(i-1)) 个结点,第i轮遍历的时间复杂度为O(2^i),因此最终时间复杂度为O(h * 2^h)

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* 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 travel(TreeLinkNode* node, int height, TreeLinkNode** lastNode, int level) {
if (!node) {
return;
}
if (height == level) {
if (*lastNode) {
(*lastNode)->next = node;
}
*lastNode = node;
return;
}
travel(node->left, height + 1, lastNode, level);
travel(node->right, height + 1, lastNode, level);
}
void connect(TreeLinkNode *root) {
TreeLinkNode* lastNode = NULL;
int level = 0;
do {
lastNode = NULL;
travel(root, 0, &lastNode, level);
level++;
} while (lastNode);
}
};