Tìm tổng lớn nhất của cây con trong cây nhị phân C++

Cho cây nhị phân có giá trị dương và âm. Nhiệm vụ: tìm tổng lớn nhất của cây con.

Mô tả: Cây con có tổng giá trị nút lớn nhất.

Ví dụ:

Đầu ra: 13

Giải thích:

Tổng cây con trái = 7
Tổng cây con phải = 1
Tổng cả cây = 13

Phương pháp giải

Duyệt hậu thứ tự (post-order). Tính tổng cây con trái/phải. Với nút hiện tại, so sánh tổng của nó với max hiện tại. Cập nhật max từ lá lên gốc.

Chương trình minh họa

Ví dụ

#include <iostream>
using namespace std;

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

Node* newNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

int calcSumTreeSumRec(Node* root, int& ans) {
    if (root == NULL)
        return 0;
    int currSum = root->key + calcSumTreeSumRec(root->left, ans) + calcSumTreeSumRec(root->right, ans);
    ans = max(ans, currSum);
    return currSum;
}

int calcMaxSubTreeSum(Node* root) {
    if (root == NULL)
        return 0;
    int ans = -100;
    calcSumTreeSumRec(root, ans);
    return ans;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(-4);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(8);
    root->right->left = newNode(-5);
    root->right->right = newNode(2);
    cout << "The largest subtree sum is " << calcMaxSubTreeSum(root);
    return 0;
}

Kết quả

The largest subtree sum is 13