C++-এ বাইনারি ট্রি-র ন্যূনতম সম আয়ত্ত লেভেল বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া থাকলে, যে লেভেলের নোডগুলোর যোগফল ন্যূনতম সেটি খুঁজে বের করতে হবে। রুট লেভেল ১, তার চাইল্ডরা লেভেল ২, এভাবে বেড়ে।

উদাহরণ: রুট=৫, লেফ্ট=৪, রাইট=-১০, এবং নিচের লেভেলগুলো। লেভেল ২-র সম = ৪ + (-১০) = -৬, যা ন্যূনতম। তাই আউটপুট ২।

সমাধানের পদ্ধতি (BFS / Level Order Traversal)

1. level = 1, sum = root->val, ansLevel = 1, ansSum = sum ইনিশিয়ালাইজ করুন।
2. একটি কিউতে রুট পুশ করুন।
3. যতক্ষন কিউ খালি নয়:
   • কারেন্ট লেভেলের নোড সংখ্যা = capacity।
   • level++, sum = 0।
   • প্রতি নোডের জন্য:
     • নোড কিউ থেকে পপ করুন।
     • রাইট চাইল্ড থাকলে এর ভ্যালু যোগ করুন এবং কিউতে পুশ করুন।
     • লেফ্ট চাইল্ড থাকলে এর ভ্যালু যোগ করুন এবং কিউতে পুশ করুন।
   • যদি sum < ansSum হয়, তবে ansSum এবং ansLevel আপডেট করুন।
4. ansLevel রিটার্ন করুন।

C++ কোড উদাহরণ

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

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

class Solution {
public:
    int solve(TreeNode* r) {
        int level = 1, sum = r->val;
        int ansLevel = level, ansSum = sum;
        queue q;
        q.push(r);
        
        while (!q.empty()) {
            int capacity = q.size();
            level++;
            sum = 0;
            while (capacity--) {
                TreeNode* node = q.front(); q.pop();
                if (node->right) {
                    sum += node->right->val;
                    q.push(node->right);
                }
                if (node->left) {
                    sum += node->left->val;
                    q.push(node->left);
                }
            }
            if (ansSum > sum) {
                ansSum = sum;
                ansLevel = level;
            }
        }
        return ansLevel;
    }
};

int main() {
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(-10);
    root->left->right = new TreeNode(-2);
    root->right->left = new TreeNode(-7);
    root->right->right = new TreeNode(15);
    Solution ob;
    cout << ob.solve(root);
    return 0;
}

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

ইনপুট: বর্ণিত ট্রি

আউটপুট: 2

জটিলতা

• সময়: O(n) — প্রতিটি নোড একবার ভিজিট করা হয়
• স্থান: O(w) — w = সর্বোচ্চ নোড সংখ্যা কোনো লেভেলে