Tổng lớn nhất từ cây nhị phân với điều kiện không chọn hai cấp liền kề trong C++

Trong bài toán này, chúng ta được cung cấp một cây nhị phân chứa các số dương. Nhiệm vụ là viết chương trình tìm tổng lớn nhất từ cây sao cho không chứa các nút từ hai cấp độ liền kề trong C++.

Mô tả vấn đề

Tìm tổng lớn nhất các nút của cây sao cho tổng không chứa các nút từ hai cấp độ liền kề của cây.

Ví dụ minh họa:

Đầu ra

21

Giải thích

• Chọn từ gốc (cấp 1): tổng = 5 + 3 + 8 + 1 = 17
• Chọn từ nút con của gốc (cấp 2): tổng = 2 + 6 + 9 + 4 = 21

Phương pháp giải

Để tìm tổng lớn nhất với điều kiện không chọn nút từ hai cấp liền kề, ta tính hai trường hợp: tổng bắt đầu từ nút gốc (cấp 1) và tổng bắt đầu từ nút con (cấp 2). Các nút tiếp theo sẽ là các nút cháu (bỏ qua cấp giữa). Sử dụng đệ quy để tìm giá trị lớn nhất.

Ví dụ chương trình

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

struct Node {
    int data;
    Node* left, *right;
    Node(int item) { data = item; }
};

int getMaxSum(Node* root);
int findSumFromNode(Node* root) {
    if (root == NULL) return 0;
    int sum = root->data;
    if (root->left != NULL) {
        sum += getMaxSum(root->left->left);
        sum += getMaxSum(root->left->right);
    }
    if (root->right != NULL) {
        sum += getMaxSum(root->right->left);
        sum += getMaxSum(root->right->right);
    }
    return sum;
}

int getMaxSum(Node* root) {
    if (root == NULL) return 0;
    return max(findSumFromNode(root), 
               (findSumFromNode(root->left) + findSumFromNode(root->right)));
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(2);
    root->right = new Node(10);
    root->left->left = new Node(4);
    root->left->right = new Node(6);
    root->right->right = new Node(9);
    cout << "Tổng lớn nhất từ cây không chọn hai cấp liền kề: " << getMaxSum(root);
    return 0;
}

Kết quả

Tổng lớn nhất từ cây không chọn hai cấp liền kề: 24