Giả sử chúng ta có một cây nhị phân và một mục tiêu số nguyên, chúng tôi phải xóa tất cả các nút lá có mục tiêu giá trị. Chúng ta phải lưu ý rằng khi chúng ta xóa một nút lá có mục tiêu giá trị nếu nút cha đó trở thành nút lá và có mục tiêu giá trị, thì nó cũng sẽ bị xóa (chúng ta cần tiếp tục làm điều đó cho đến khi chúng ta không thể). Vì vậy, nếu cây giống như bên dưới và mục tiêu là 2, thì cây cuối cùng sẽ giống như cây cuối cùng -
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức đệ quy được gọi là remLeaf (), phương thức này sẽ lấy gốc và đích
-
nếu gốc là null, thì trả về null
-
left:=remLeaf (left of root, target)
-
right:=remLeaf (bên phải của thư mục gốc, target)
-
nếu bên trái là null và bên phải là null và giá trị của root giống với đích thì trả về null
-
left of root:=left
-
quyền của root:=right
-
trả về thư mục gốc
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = 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;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
} else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr->val == 0 || curr == NULL){
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* removeLeafNodes(TreeNode* root, int target) {
if(!root || root->val == 0) return NULL;
TreeNode* left = removeLeafNodes(root->left, target);
TreeNode* right = removeLeafNodes(root->right, target);
if(!left && !right && root->val == target){
return NULL;
}
root->left = left;
root->right = right;
return root;
}
};
main() {
vector<int> v1 = {1,2,3,2,NULL,2,4};
TreeNode *root = make_tree(v1);
Solution ob;
tree_level_trav(ob.removeLeafNodes(root, 2));
} Đầu vào
[1,2,3,2,null,2,4] 2
Đầu ra
[1, 3, 4, ]