Giả sử chúng ta có một cây nhị phân; chúng tôi phải chuyển đổi danh sách này thành một danh sách được liên kết riêng (tại chỗ).
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
ser pres:=null
-
Xác định một hàm đệ quy giải quyết (), sẽ lấy gốc làm đầu vào.
-
nếu root là null, thì trả về
-
giải quyết (quyền root)
-
giải quyết (bên trái của thư mục gốc)
-
right of root:=pres, left of root:=null
-
trước:=root
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
TreeNode* prev = NULL;
void flatten(TreeNode* root) {
if(!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = NULL;
prev = root;
}
};
main(){
vector<int> v = {1,2,5,3,4};
TreeNode *root = make_tree(v);
Solution ob;
(ob.flatten(root));
TreeNode *ptr = root;
while(ptr != NULL && ptr->val != 0){
cout << ptr->val << ", ";
ptr = ptr->right;
}
} Đầu vào
{1,2,5,3,4} Đầu ra
1, 2, 3, 4, 5,