Chuyển đổi BST sang Greater Tree trong C ++

Giả sử chúng ta có Cây tìm kiếm nhị phân, chúng ta phải chuyển đổi nó thành Cây lớn hơn sao cho mọi khóa của BST ban đầu được thay đổi thành khóa ban đầu + tổng của tất cả các khóa lớn hơn khóa ban đầu trong BST.

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 -

• Xác định một hàm revInorder (), hàm này sẽ lấy gốc cây và s,

• nếu root là null, thì -

  • trở lại

• revInorder (quyền của root, s)

• s:=s + val của root

• val của root:=s

• revInorder (bên trái của thư mục gốc, s)

• Từ phương thức chính, thực hiện như sau -

• nếu root là null, thì -

  • trả về null

• tổng:=0

• revInorder (root, sum)

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để 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 = 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:
   void revInorder(TreeNode *root,int &s){
      if (root == NULL || root->val == 0)
         return;
      revInorder(root->right, s);
      s += root->val;
      root->val = s;
      revInorder(root->left, s);
   }
   TreeNode* convertBST(TreeNode* root){
      if (root == NULL || root->val == 0)
         return NULL;
      int sum = 0;
      revInorder(root, sum);
      return root;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,2,8,NULL,NULL,6,9};
   TreeNode *root = make_tree(v);
   tree_level_trav(ob.convertBST(root));
}

Đầu vào

{5,2,8,NULL,NULL,6,9}

Đầu ra

[28, 30, 17, null, null, 23, 9, ]