Tổng lớn nhất các nút trong cây nhị phân không có hai nút liền kề trong C++

Cho cây nhị phân. Tìm tập con nút có tổng lớn nhất sao cho không có hai nút nào trực tiếp kết nối (cha-con).

Thuật toán (DP trên cây + Memoization)

• Với mỗi nút, hai trạng thái:
  • incl: chọn nút này → không chọn con, nhưng chọn cháu.
  • excl: không chọn nút này → chọn tối ưu từ con.
• Dùng map lưu kết quả đã tính (memoization).
• Trả về max(incl, excl) tại gốc.

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

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

struct node { int data; node *left, *right; };
node* newNode(int data) {
    node* temp = new node;
    temp->data = data; temp->left = temp->right = NULL;
    return temp;
}

int getMaxSumUtil(node* node, map<node*, int>& mp) {
    if (!node) return 0;
    if (mp.count(node)) return mp[node];
    int incl = node->data;
    if (node->left) incl += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
    if (node->right) incl += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
    int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
    return mp[node] = max(incl, excl);
}

int getMaxSum(node* node) {
    if (!node) return 0;
    map<node*, int> mp;
    return getMaxSumUtil(node, mp);
}

int main() {
    node* root = newNode(1);
    root->left = newNode(2); root->right = newNode(3);
    root->right->left = newNode(4); root->right->right = newNode(5);
    root->left->left = newNode(1);
    cout << getMaxSum(root) << endl;
    return 0;
}

Đầu ra

11