使用 C++ 删除具有给定值的叶子节点

c++server side programmingprogramming

假设我们有一个二叉树和一个整数目标，我们必须删除所有具有目标值的叶子节点。我们必须记住，一旦我们删除具有目标值的叶子节点，如果它的父节点成为叶子节点并具有目标值，它也应该被删除(我们需要继续这样做，直到我们不能删除为止)。因此，如果树如下所示，目标是 2，那么最终的树将像最后一个 −

为了解决这个问题，我们将遵循以下步骤 −

定义一个名为 remLeaf() 的递归方法，它将获取根和目标
如果根为空，则返回 null
left := remLeaf(root 的左侧，目标)
right := remLeaf(root 的右侧，目标)
如果左侧为空且右侧为空且根的值与目标相同，则返回 null
根的左侧 := left
根的右侧 := right
返回 root

示例 (C++)

让我们看下面的实现，以便更好地理解 −

#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));
}