Cây tìm kiếm nhị phân đến cây tổng lớn hơn trong C ++

Giả sử chúng ta có gốc của cây tìm kiếm nhị phân với các giá trị khác nhau, chúng ta phải sửa đổi nó để mọi nút đều có giá trị mới bằng tổng các giá trị của cây ban đầu lớn hơn hoặc bằng giá trị của nút. Chúng ta phải lưu ý rằng chúng ta đang xử lý cây tìm kiếm nhị phân và điều này sẽ duy trì các thuộc tính của BST. Vì vậy, nếu cây đầu vào giống như -

Khi đó cây đầ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 -

• đặt toàn cầu:=0

• Xác định một hàm đệ quy giải quyết (), sẽ lấy gốc làm đầu vào.

• nếu quyền của người chủ không phải là null, thì giải quyết (quyền của người gốc)

• global:=global + giá trị của root

• nếu bên trái của thư mục gốc không phải là null, thì giải quyết (bên trái của thư mục gốc)

• trả về thư mục gốc

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;
}
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 == NULL || curr->val == 0){
            cout << "null" << ", ";
         }else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   int global = 0;
   TreeNode* bstToGst(TreeNode* root) {
      if(root->right)bstToGst(root->right);
      if(root->val != 0)
      root->val = global = global + root->val;
      if(root->left)bstToGst(root->left);
      return root;
   }
};
main(){
   vector<int> v =
   {4,1,6,1,2,5,7,NULL,NULL,NULL,3,NULL,NULL,NULL,8};
   TreeNode *root = make_tree(v);
   Solution ob;
   tree_level_trav(ob.bstToGst(root));
}

Đầu vào

[4,1,6,1,2,5,7,null,null,null,3,null,null,null,8]

Đầu ra

[30, 36, 21, 37, 35, 26, 15, null, null, null, 33, null, null, null,
8, ]