Chuyển đổi cây nhị phân sao cho mỗi nút lưu tổng các nút trong cây con phải của nó trong C++

Cho một cây nhị phân, hãy biến đổi nó sao cho giá trị của mỗi nút trở thành tổng của giá trị gốc của nút đó và tất cả các nút trong cây con phải của nó.

Giải pháp: Duyệt post-order (trái - phải - gốc). Tại mỗi nút, tính tổng cây con phải, cộng vào giá trị nút, trả về tổng của cả cây con (để cha sử dụng).

Ví dụ minh họa (C++)

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

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

Node* createNode(int item) {
    Node* temp = new Node();
    temp->data = item;
    temp->left = temp->right = nullptr;
    return temp;
}

// Trả về tổng của cây con gốc tại root (sau khi đã cập nhật)
int rightsum_tree(Node* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->data;
    int rightSum = rightsum_tree(root->right);
    int leftSum = rightsum_tree(root->left);
    root->data += rightSum;          // Cộng tổng cây con phải vào nút hiện tại
    return root->data + leftSum;     // Trả về tổng cả cây con này
}

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

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    rightsum_tree(root);
    cout << "Cay nhi phan sau khi cap nhat (inorder): ";
    inorder(root);
    return 0;
}

Kết quả

Cay nhi phan sau khi cap nhat (inorder): 4 7 5 10 9 6

Giải thích: Nút 6 (lá phải) giữ 6. Nút 3 = 3+6=9. Nút 5 (lá) giữ 5. Nút 4 (lá) giữ 4. Nút 2 = 2+5=7. Nút 1 = 1+9=10.