পাথ সম IV (বাইনারি ট্রি রিপ্রেজেন্টেশন) C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রিকে ৩-ডিজিট ইন্টিজার লিস্ট দিয়ে রিপ্রেজেন্ট করা হয়ে থাকে (ডেপথ < 5)। প্রতিটি ইন্টিজার D P V ফরম্যাটে:

• D (হান্ড্রেডস) = ডেপথ (১-৪)
• P (টেনস) = পজিশন ইন লেভেল (১-৮, ফুল বাইনারি ট্রি মত)
• V (ইউনিটস) = নোড ভ্যালু (০-৯)

উদাহরণ

ইনপুট: [113, 215, 221]

ট্রি:

    3 (depth 1, pos 1)
   / \
  5   1 (depth 2, pos 1 & 2)

অ্যালগরিদম: DFS

1. ইনপুট থেকে লেভেলভিত্তিক গ্রাফ বানান: graph[level] = vector<pair<pos, val>>। পজিশন কোড: (1 << (level-1)) + pos - 1।
2. রুট থেকে DFS চালান। প্রতিটি নোডের জন্য চাইল্ড খুঁজুন: child.pos / 2 == parent.pos।
3. যদি চাইল্ড না থাকে (লিফ), তো currSum + nodeVal আন্সারে যোগ করুন।

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

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

class Solution {
public:
    int ans = 0;
    map<int, vector<pair<int,int>>> graph;

    void dfs(int nodeVal, int level, int pos, int sum = 0) {
        bool isLeaf = true;
        for (auto& [cPos, cVal] : graph[level+1]) {
            if (cPos / 2 == pos) {
                isLeaf = false;
                dfs(cVal, level+1, cPos, sum + nodeVal);
            }
        }
        if (isLeaf) ans += sum + nodeVal;
    }

    int pathSum(vector<int>& nums) {
        ans = 0;
        graph.clear();
        for (int x : nums) {
            int val = x % 10; x /= 10;
            int pos = x % 10; x /= 10;
            int level = x;
            int encodedPos = (1 << (level-1)) + pos - 1;
            graph[level].push_back({encodedPos, val});
        }
        dfs(graph[1][0].second, 1, graph[1][0].first);
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {113, 215, 221};
    cout << ob.pathSum(v); // আউটপুট: 12
    return 0;
}

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

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

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