Thêm tất cả giá trị lớn hơn vào mỗi nút trong BST

BST (cây tìm kiếm nhị phân) là cây nhị phân mà nút trái nhỏ hơn gốc, nút phải lớn hơn gốc. Bài toán: lấy cây nhị phân, cộng tất cả giá trị lớn hơn nút hiện tại vào nút đó. Tức là với BST, cộng vào mỗi nút tổng giá trị các nút lớn hơn nó.

Đầu vào

    10
   /  \
  5    20
 / \  / \
1  7 15 25

Đầu ra

    70
   /  \
 82    45
 / \  / \
83 77 60 25

Giải thích

Chương trình chuyển BST thành cây nhị phân với giá trị nút bằng tổng các phần tử lớn hơn cộng giá trị gốc của nút.

Giải pháp: dùng duyệt inorder ngược (đệ quy cây con phải trước, rồi gốc, rồi cây con trái) và giữ biến sum lưu tổng các nút đã duyệt. Dùng sum để sửa giá trị nút hiện tại: trước cộng giá trị nút vào sum, sau đó gán giá trị nút = sum.

Ví dụ

#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 sau:
        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;
}