C++ Cây con lớn nhất có số 0 và 1 bằng nhau

Cho cây nhị phân chỉ chứa 0 và 1. Tìm cây con lớn nhất có số 0 và 1 bằng nhau.

Phương pháp giải

Thay 0 → -1. Bài toán trở thành tìm cây con lớn nhất có tổng = 0. Duyệt hậu tự, tính tổng và kích thước cây con tại mỗi nút. Cập nhật max_size khi tổng = 0.

Ví dụ minh họa

#include <iostream>
using namespace std;

int maxi = -1;

struct node {
    int data;
    node *left, *right;
};

node* newnode(int key) {
    node* t = new node();
    t->data = key; t->left = t->right = NULL;
    return t;
}

int calc_sum(node* root) {
    if (!root) return 0;
    if (root->data == 0) root->data = -1;
    int a = calc_sum(root->left);
    int b = calc_sum(root->right);
    root->data += a + b;
    return root->data;
}

int calculatingmax(node* root) {
    if (!root) return 0;
    int a = calculatingmax(root->right) + 1;
    int b = calculatingmax(root->left);
    a += b;
    if (root->data == 0 && a >= maxi) maxi = a;
    return a;
}

int main() {
    node* root = newnode(1);
    root->right = newnode(0);
    root->right->right = newnode(1);
    root->right->right->right = newnode(1);
    root->left = newnode(0);
    root->left->left = newnode(1);
    root->left->left->left = newnode(1);
    root->left->right = newnode(0);
    root->left->right->left = newnode(1);
    root->left->right->left->left = newnode(1);
    root->left->right->right = newnode(0);
    root->left->right->right->left = newnode(0);
    root->left->right->right->left->left = newnode(1);

    calc_sum(root);
    calculatingmax(root);
    cout << maxi;
    return 0;
}

Kết quả

6

Giải thích

Đổi 0→-1, tính tổng cây con cho mỗi nút. Duyệt lại tìm nút có tổng=0 và kích thước lớn nhất.

Kết luận

Đã giải bài toán cây con lớn nhất số 0=1 bằng biến đổi 0→-1 và tìm cây con tổng=0. Code C++ áp dụng cho các ngôn ngữ khác. Hy vọng hữu ích.