Cộng tất cả giá trị lớn hơn vào mỗi nút của BST C++

Cho một cây tìm kiếm nhị phân (BST). Cần biến đổi cây sao cho mỗi nút chứa giá trị gốc cộng với tổng tất cả các giá trị lớn hơn nó trong cây.

Giải thuật

Sử dụng duyệt inorder ngược (Right-Root-Left) để duyệt các nút theo thứ tự giảm dần. Duy trì biến sum lưu tổng các nút đã duyệt. Tại mỗi nút: sum += node->data; node->data = sum.

Ví dụ minh họa

#include <iostream>
using namespace std;

struct node {
    int data;
    node *left;
    node *right;
};

node *newNode(int key) {
    node *temp = new node;
    temp->left = NULL;
    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() {
    /* Tạo 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);
    
    Inorder(root); cout << endl;
    AddGreater(root);
    Inorder(root); cout << endl;
    return 0;
}