Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chuyển cây tìm kiếm nhị phân thành cây tổng lớn hơn (Binary Search Tree to Greater Sum Tree) trong C++


Cho gốc của cây tìm kiếm nhị phân (BST) với các giá trị phân biệt, sửa đổi sao cho mỗi node có giá trị mới bằng tổng các giá trị của cây gốc lớn hơn hoặc bằng giá trị node đó. Phải giữ tính chất BST.

Ví dụ: cây đầu vào -> cây đầu ra với giá trị cập nhật.

Giải pháp: duyệt ngược in-order (right-root-left) tích lũy tổng toàn cục.

  • Biến global = 0.

  • Hàm đệ quy solve(root): nếu right tồn tại -> solve(right); global += root->val; root->val = global; nếu left tồn tại -> solve(left); trả về root.

Ví dụ hoàn chỉnh

#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) { q.push(NULL); }
        else {
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
            if (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, ]