题目
给定一个二叉树,原地将它展开为链表。
例如,给定二叉树
1
2
3
4
5 1
/ \
2 5
/ \ \
3 4 6将其展开为:
1
2
3
4
5
6
7
8
9
10
11 1
\
2
\
3
\
4
\
5
\
6来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
- 题目要求为原地展开为链表,不能暴力地遍历一遍复制节点构造新链表。
迭代
将二叉树展成单向链表的过程也是构造线索二叉树的过程,核心思想为:利用节点中空的左子节点和右子节点,把空的右子节点指向后继节点。由于后继节点的深度可能与当前节点深度相同或小于当前深度,用迭代似乎比较合理。
遍历二叉树的顺序为前序遍历,我们要做的是在迭代的过程中,将当前节点迭代为左子节点之前,将右子节点入栈(作为左子树最右节点的后继节点),若右子节点为空,那么右子节点指向栈顶,将当前节点迭代为右子节点,出栈;若栈为空,说明没有后继节点,结束。若左子节点不为空,还需将右子节点置空;若左子节点为空,出栈,当前节点迭代为右子节点;
注意题目给出的测试用例隐藏的信息是:左子节点全部置空,只保留右子节点作为链表只想下个节点的指针。
迭代代码如下:
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
36
37
38/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if(!root) return;
stack<TreeNode*> sta;
while(!sta.empty() || root){
if(root->left){// 左子节点不为空,则右子节点入栈,断开右子节点
if(root->right) sta.push(root->right);
root->right = root->left;
root->left = nullptr;
root = root->right;// 更新当前节点为左子节点(后继节点(如有)已入栈)
}
else{// 左子节点为空
if(root->right) root = root->right;// 右子节点非空
else{// 右子节点为空
if(!sta.empty()){
root->right = sta.top();
root = root->right;
sta.pop();
}
else break;
}
}
}
}
};时间复杂度:每个节点访问以此,因此时间复杂度为
O(N)
;空间复杂度为栈的大小,O(logN)
,因为深度增加1是才有可能将右子节点入栈。
莫里斯遍历
而类似莫里斯遍历的思路,在破坏二叉树结构的基础上进行遍历,并且不用额外的内存空间,步骤如下:
- while 当前节点不为空:
- 对于当前根节点:将右子树取下,将左子树接到右子树的位置;
- 把右子树接到左子树的最右节点的右子节点;
- 更新右子节点为当前节点;
时间复杂度
O(N)
,空间复杂度O(1)
。代码如下:
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/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if(!root) return;
while(root){
if(!root->left) root = root->right;
else{
auto cur = root->left;
while(cur->right) cur = cur->right;
cur->right = root->right;
root->right = root->left;
root->left = nullptr;
}
}
}
};
递归
不出所料,递归也是可行的。具体思路:
展开是按照前序遍历,后继节点作为本节点的右子节点,那么我们倒过来遍历(不是后序遍历,而是右->根->左),把这样“逆序”遍历的上一个节点作为下一个节点的右子节点;
时间复杂度
O(N)
,空间复杂度O(1)
;代码:
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/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
Solution(): pre(nullptr) {}
void flatten(TreeNode* root) {
if(!root) return;
flatten(root->right);
flatten(root->left);
root->right = pre;
root->left = nullptr;
pre = root;
}
private:
TreeNode* pre;
};
总结
- 迭代法的核心思路是利用了 前序遍历的右子节点是左子树最右节点的后继节点 的特征;
- 莫里斯遍历的核心思路就是 将根节点、左子树整体、右子树整体按照根->左->右的顺序排成单向链表;
- 递归的思路就是 把前序遍历逆转过来,按照右->左->根的顺序,从尾到头构造单向链表,因为这种遍历顺序与链表顺序刚好是逆向的,所以只需把当前节点的右子节点指向上一个节点即可。