เพิ่มค่าของโหนดที่มากกว่าใน BST ให้กับทุกโหนดใน C++

ปัญหา

ให้ Binary Search Tree (BST) ต้องการแปลงให้แต่ละโหนดมีค่าใหม่ = ค่าเดิม + ผลรวมของโหนดที่มีค่ามากกว่ามันทั้งหมด

นี่คือการแปลง BST เป็น "Greater Sum Tree"

วิธีแก้ปัญหา: Reverse Inorder Traversal

ใช้การท่องในออร์เดอร์แบบกลับ (Right → Root → Left) เพื่อเยี่ยมชมโหนดจากค่ามากไปน้อย:

1. ท่องด้านขวาก่อน (ค่ามากกว่า)
2. สะสมผลรวม (sum) ของโหนดที่ผ่านมาแล้ว
3. อัปเดตค่าโหนดปัจจุบัน = sum + ค่าเดิม
4. ท่องด้านซ้ายต่อ

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int key) {
    Node* temp = new Node;
    temp->left = temp->right = NULL;
    temp->data = key;
    return temp;
}

void Inorder(Node* root) {
    if (!root) return;
    Inorder(root->left);
    cout << root->data << " ";
    Inorder(root->right);
}

Node* Insert(Node* root, int key) {
    if (!root) return newNode(key);
    if (key < root->data)
        root->left = Insert(root->left, key);
    else
        root->right = Insert(root->right, key);
    return root;
}

void RevInorderAdd(Node* root, int& sum) {
    if (!root) return;
    RevInorderAdd(root->right, sum);
    sum += root->data;
    root->data = sum;
    RevInorderAdd(root->left, sum);
}

void AddGreater(Node* root) {
    int sum = 0;
    RevInorderAdd(root, sum);
}

int main() {
    // สร้าง BST:       10
    //              /      \
    //             5        20
    //            / \      /  \
    //           1   7    15   25
    Node* root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);
    
    cout << "Inorder traversal ก่อนแปลง: ";
    Inorder(root);
    cout << endl;
    
    AddGreater(root);
    
    cout << "Inorder traversal หลังแปลง: ";
    Inorder(root);
    cout << endl;
    return 0;
}

ผลลัพธ์

Inorder traversal ก่อนแปลง: 1 5 7 10 15 20 25
Inorder traversal หลังแปลง: 82 81 76 69 54 45 25