แปลง Binary Search Tree ให้เป็น Greater Sum Tree ใน C++

โจทย์: กำหนด root ของ binary search tree (BST) ที่มีค่า distinct (ไม่ซ้ำ) ให้ ปรับเปลี่ยนค่าของทุกโหนด ให้เป็นผลรวมของค่าทั้งหมดในต้นไม้เดิมที่ >= ค่าของโหนดนั้น ต้องรักษาคุณสมบัติ BST ไว้

ตัวอย่าง

กลายเป็น:

แนวทางแก้ปัญหา (Reverse Inorder Traversal)

1. กำหนดตัวแปร global sum = 0
2. สร้างฟังก์ชัน recursive solve(root):
   • ถ้ามี right child: เรียก solve(right)
   • sum += root->val, ตั้งค่า root->val = sum
   • ถ้ามี left child: เรียก solve(left)
3. เรียก solve(root) และคืน root

เหตุผล: Inorder traversal ของ BST ให้ค่าเรียงน้อยไปมาก Reverse inorder (Right -> Root -> Left) ให้ค่ามากไปน้อย สะสมผลรวมไปเรื่อยๆ จะได้ค่าที่ต้องการ

ตัวอย่างโค้ดเต็ม

#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) return;
    cout << "[";
    queue<TreeNode*> q;
    q.push(root); q.push(NULL);
    while(q.size() > 1) {
        TreeNode *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;
    }
};

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

Input

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

Output

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