Tổng cha-con lớn nhất trong cây nhị phân C++

Cho cây nhị phân. Tìm max của (giá trị nút cha + giá trị 2 nút con) среди tất cả các nút có đủ 2 con.

Thuật toán (DFS)

• Duyệt post-order.
• Nếu nút có cả 2 con: tính tổng = node->data + left->data + right->data.
• Cập nhật max toàn cục.
• Trả về max của cây con trái, phải và tổng tại nút hiện tại.

Ví dụ triển khai (C++)

#include <iostream>
using namespace std;

struct Node { int data; Node *left, *right; };
Node* newNode(int n) {
    Node* root = new Node();
    root->data = n; root->left = root->right = NULL;
    return root;
}

int maxSum(Node* root) {
    if (!root) return 0;
    int res = maxSum(root->left);
    if (root->left && root->right) {
        int sum = root->data + root->left->data + root->right->data;
        res = max(res, sum);
    }
    return max(res, maxSum(root->right));
}

int main() {
    Node* root = newNode(15);
    root->left = newNode(16);
    root->left->left = newNode(8);
    root->left->left->left = newNode(55);
    root->left->right = newNode(67);
    root->left->right->left = newNode(44);
    root->right = newNode(17);
    root->right->left = newNode(7);
    root->right->left->right = newNode(11);
    root->right->right = newNode(41);
    cout << maxSum(root);
    return 0;
}

Đầu ra

91