Phân chia cây bằng nhau trong C++

Giới thiệu

Cho cây nhị phân. Kiểm tra có thể cắt đúng 1 cạnh để chia thành 2 cây có tổng giá trị nút bằng nhau hay không.

Ý tưởng

Tổng toàn cây = S. Cắt cạnh cha-con tạo ra 2 cây con với tổng x và S-x. Cần x = S-x → x = S/2. Do đó: S phải chẵn, và tồn tại một cây con (không phải toàn cây) có tổng = S/2.

Thuật toán: Post-order DFS

1. DFS tính tổng mỗi cây con, lưu vào stack/list.
2. Tổng toàn cây = phần tử cuối (gốc).
3. Kiểm tra xem có tổng nào trong danh sách (trừ gốc) bằng S/2 không.

Cài đặt C++

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    vector<int> sums;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        int cur = node->val + left + right;
        sums.push_back(cur);
        return cur;
    }
public:
    bool checkEqualTree(TreeNode* root) {
        dfs(root);
        int total = sums.back(); sums.pop_back(); // bỏ gốc
        if (total % 2 != 0) return false;
        int half = total / 2;
        for (int s : sums) if (s == half) return true;
        return false;
    }
};

int main() {
    // Cây: 5 / \ 10 10 / \ 2 3
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(10);
    root->right = new TreeNode(10);
    root->right->left = new TreeNode(2);
    root->right->right = new TreeNode(3);
    Solution ob;
    cout << ob.checkEqualTree(root); // Output: 1 (true)
    return 0;
}

Phân tích

• Thời gian: O(N).
• Không gian: O(N) – lưu tổng các cây con.

LeetCode 663 "Equal Tree Partition".