বাইনারি ট্রি সমান পার্টিশান করা C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া আছে। ঠিক একটি এজ মুছে দিয়ে ট্রিকে দুটি পার্টে ভাগ করা যাবে কিনা যাতে দুটি পার্টের নোড ভ্যালু সাম সমান হয়।

উদাহরণ

ট্রি:

    5
   / \
  10  10
     /  \
    2    3

অ্যালগরিদম: পোস্ট-অর্ডার ট্রাভার্সাল + স্ট্যাক

1. পোস্ট-অর্ডার ট্রাভার্সাল দিয়ে প্রতিটি সাবট্রির সাম বের করুন এবং স্ট্যাকে পুশ করুন।
2. রুটের সাম = টোটাল সাম।
3. স্ট্যাক থেকে পপ করে প্রতিটি সাবট্রি সাম x এর জন্য চেক করুন: x == totalSum - x হলে true।
4. যদি কোনো সাবট্রি সাম টোটালের অর্ধেক হয়, তবে সেটি প্যারেন্ট থেকে কাটা যাবে।

C++ বাস্তবায়ন

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    stack<int> st;

    int solve(TreeNode* node) {
        if (!node) return 0;
        int leftSum = solve(node->left);
        int rightSum = solve(node->right);
        int curr = node->val + leftSum + rightSum;
        st.push(curr);
        return curr;
    }

    bool checkEqualTree(TreeNode* root) {
        solve(root);
        int total = st.top(); st.pop();
        while (!st.empty()) {
            int x = st.top(); st.pop();
            if (x == total - x) return true;
        }
        return false;
    }
};

int main() {
    Solution ob;
    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);
    cout << ob.checkEqualTree(root); // আউটপুট: 1 (true)
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N) — N = নোড সংখ্যা।
• স্থান জটিলতা: O(N) — রিকার্সন স্ট্যাক ও সাবট্রি সাম স্ট্যাক।