题目描述
给定一个二叉树，原地将它展开为一个单链表。
树节点的定义为：
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) {}
};
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6
方法一：前序遍历
按照前序遍历，依次将访问到的节点存入一个队列中，然后，将队列按序连起来，即得到展开后的链表。
前序遍历实现有两种方法，一种递归实现，一种非递归实现：
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
vector<TreeNode*> list;
public:
void flatten(TreeNode* root) {
DFS(root, list);
for(int i=1; i<list.size(); i++){
TreeNode *pre = list[i-1], *cur = list[i];
pre->left = nullptr;
pre->right = cur;
}
}
void DFS(TreeNode *root, vector<TreeNode*> list) {
if(root != nullptr){
list.push_back(root);
DFS(root->left, list);
DFS(root->right, list);
}else return;
}
};
|
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void flatten(TreeNode* root) {
auto list = vector<TreeNode*>();
auto stk = stack<TreeNode*>();
TreeNode *node = root;
while(node != nullptr || !stk.empty()){
while(node != nullptr){
list.push_back(node);
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
node = node->right;
}
for(int i=1; i<list.size(); i++){
TreeNode *pre = list[i-1], *cur = list[i];
pre->left = nullptr;
pre->right = cur;
}
}
};
|
方法二：前序遍历和展开同时进行
将二叉树的左右子树看作一个整体，暂时忽略其内部结构，在访问了根节点后，我们要先遍历左子树，再遍历右子树，所以，如果先将右子树压入栈中，再将左子树压入栈中，那么退栈时，一定会先返回左子树（即先遍历左子树）。我们只需要将各个子树的根压入栈中即可。最后再使用递归思想，对每个子树也执行这样的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
void flatten(TreeNode *root) {
TreeNode *pre = nullptr, *cur;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
cur = stk.top();
stk.pop();
if(pre != nullptr){
pre->left = nullptr;
pre->right = cur;
}
if(cur->right != nullptr)
stk.push(cur->right);
if(cur->left != nullptr)
stk.push(cur->left);
pre = cur;
}
}
};
|
方法三：寻找前驱节点
由于先序遍历的特性，我们总是先访问根，然后左子树，最后右子树，这就意味着，即是是右子树中最先被访问的（即右子树的根），也比左子树中最后被访问的还要后被访问。所以，我们可以直接将左子树中最右的子树当作右子树的前驱节点，即让左子树最右的节点的右指针指向右子树的根节点，然后让整体的根节点的右指针，指向左子树的根节点。然后按照此方法，依次访问后面的节点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution{
public:
void flatten(TreeNode *root){
TreeNode *cur = root;
while(cur != nullptr){
if(cur->left != nullptr){
TreeNode *pre = cur->left;
while(pre->right != nullptr)
pre = pre->right;
pre->right = cur->right;
cur->right = cur->left;
cur->left = nullptr;
}
cur = cur->right;
}
}
};
|
