Convert BST to Greater Tree trong C++

Cho cây nhị phân tìm kiếm (BST), hãy chuyển đổi thành "Greater Tree" sao cho mỗi nút mang giá trị = giá trị gốc + tổng tất cả các giá trị lớn hơn nó trong BST.

Ví dụ minh họa qua hình ảnh (cây gốc và cây sau chuyển đổi).

Giải thuật: Duyệt Inorder Ngược (Reverse Inorder)

Duyệt theo thứ tự: Phải → Gốc → Trái. Duy trì biến cộng dồn sum.

1. Nếu nút null, trả về.
2. Duyệt cây con phải.
3. Cập nhật sum += node->val, gán node->val = sum.
4. Duyệt cây con trái.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    void revInorder(TreeNode* root, int& sum) {
        if (!root) return;
        revInorder(root->right, sum);
        sum += root->val;
        root->val = sum;
        revInorder(root->left, sum);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        revInorder(root, sum);
        return root;
    }
};

// Helper: xây cây từ mảng level-order (0 đại diện null)
TreeNode* buildTree(vector<int> v) {
    if (v.empty() || v[0] == 0) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < v.size() && v[i] != 0) {
            cur->left = new TreeNode(v[i]);
            q.push(cur->left);
        }
        i++;
        if (i < v.size() && v[i] != 0) {
            cur->right = new TreeNode(v[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

// Helper: in level-order
void printLevel(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    cout << "[";
    bool first = true;
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (cur) {
            if (!first) cout << ", ";
            cout << cur->val;
            first = false;
            q.push(cur->left);
            q.push(cur->right);
        } else {
            if (!first) cout << ", ";
            cout << "null";
            first = false;
        }
    }
    cout << "]" << endl;
}

int main() {
    Solution ob;
    vector<int> v = {5,2,8,0,0,6,9}; // 0 = null
    TreeNode* root = buildTree(v);
    printLevel(ob.convertBST(root)); // [28, 30, 17, null, null, 23, 9]
    return 0;
}

Đầu vào / Đầu ra

Input: {5,2,8,NULL,NULL,6,9}
Output: [28, 30, 17, null, null, 23, 9]