Convert BST to Greater Tree ใน C++

แนวคิด

สมมติว่ามี Binary Search Tree ให้แปลงเป็น Greater Tree โดยทุก key ของ BST เดิมจะเปลี่ยนเป็น key เดิม + ผลรวมของ key ทั้งหมดที่มากกว่า key เดิมใน BST

เช่น ถ้าอินพุตเป็น:

ผลลัพธ์จะเป็น:

วิธีแก้:

• กำหนดฟังก์ชัน revInorder() รับ root และ s
• ถ้า root เป็น null: คืนค่า
• revInorder(right of root, s)
• s := s + val of root
• val of root := s
• revInorder(left of root, s)
• จากเมธอดหลัก:
  • ถ้า root เป็น null: คืนค่า null
  • sum := 0
  • revInorder(root, sum)
  • คืนค่า root

ตัวอย่าง

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

อินพุต

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

เอาต์พุต

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