แปลง Binary Tree ให้แต่ละโหนดเก็บผลรวมของ Right Subtree ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง Binary Tree ให้แต่ละโหนดเก็บผลรวมของโหนดทั้งหมดใน Right Subtree ของมัน

เราจะได้รับ Binary Tree มา 1 ต้น งานคือคืนต้นไม้อีกต้นหนึ่งที่ทุกโหนดมีค่าเท่ากับผลรวมของโหนดนั้นเองและ Right Subtree ของมัน

ตัวอย่างโค้ด

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

// โครงสร้างโหนดของต้นไม้
struct Node {
    int data;
    Node *left, *right;
};

// สร้างโหนดใหม่
struct Node* createNode(int item) {
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

// สร้าง Binary Tree ใหม่ที่มีค่าผลรวม Right Subtree
int rightsum_tree(Node* root) {
    if (!root)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;

    // เปลี่ยนค่าของ Left/Right Subtree
    int rightsum = rightsum_tree(root->right);
    int leftsum = rightsum_tree(root->left);

    // บวกผลรวมของ Right Subtree
    root->data += rightsum;

    return root->data + leftsum;
}

// ท่องต้นไม้แบบ Inorder
void inorder(struct Node* node) {
    if (node == NULL)
        return;
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}

int main() {
    struct Node* root = NULL;
    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 << "Updated Binary Tree :\n";
    inorder(root);
    return 0;
}

ผลลัพธ์

Updated Binary Tree : 4 7 5 10 9 6