মডিউল ১৯-৩ঃ Left View Of a Binary Tree (Coding Ninjas)

প্রবলেম লিংকঃ Left View Of a Binary Tree - Coding Ninjas

প্রবলেম স্টেটমেন্টঃ একটি বাইনারি ট্রি দেওয়া থাকবে। তার লেফট ভিউ প্রিন্ট করতে হবে। অর্থাৎ লেফট সাইড থেকে দেখলে যেই নোডগুলো দেখা যাবে তা প্রিন্ট করতে হবে। সোজা ভাবে বললে প্রতিটি লেভেল এর প্রথম নোডটি প্রিন্ট করতে হবে। সল্যুশনঃ এটিও আমরা লেভেল অর্ডার ট্রাভারসাল দিয়ে করে ফেলতে পারি। প্রতিটি লেভেলে যেয়ে তার প্রথম নোডটি প্রিন্ট করে দিব। কোন একটি লেভেলে প্রথম বার আসা হয়েছে কিনা তা বুঝার জন্য আমরা একটি বুলিয়ান এরে মেইনটেইন করব। যদি সেই লেভেলে আগে এসে থাকি তাহলে সেটি কিউতে পুশ করব না। আর যদি সেই লেভেলে প্রথমবার আসি তাহলে পুশ করে দিব।

#include <bits/stdc++.h>
vector<int> getLeftView(TreeNode<int> *root)
{
    bool frq[3005] = {false};    // কোন একটি লেভেলে প্রথম বার আসা হয়েছে কিনা তা বুঝার জন্য আমরা একটি বুলিয়ান এরে নেওয়া হচ্ছে। কোশ্চেনের কনস্ট্রেইন্ট অনুযায়ী তার সাইজ দেওয়া হয়েছে।
    queue<pair<TreeNode<int> *, int>> q;     // নোড এবং লেভেল স্টোর করার জন্য পেয়ার টাইপের কিউ নেওয়া হয়েছে।
    if (root)
        q.push({root, 1});         // রুটকে কিউ তে পুশ করা হচ্ছে লেভেল ১ দিয়ে।
    vector<int> v;           // লেফট ভিউ এর নোড গুলো একটি ভেক্টরে করে রিটার্ন করতে বলা হয়েছে তাই ভেক্টর নিয়ে নেওয়া হয়েছে।
    while (!q.empty())
    {
        pair<TreeNode<int> *, int> pr = q.front();   
        q.pop();
        TreeNode<int> *node = pr.first;   // পেয়ার এর প্রথম এলিমেন্টটি হচ্ছে নোড।
        int level = pr.second;          // দ্বিতীয়টি হচ্ছে লেভেল।

        if (frq[level] == false)      // যদি এরেতে এই লেভেল এর মান ফলস হয় তারমানে এই লেভেলে এর আগে আসা হয়নি।
        {
            v.push_back(node->data);   // যেহেতু এটি এই লেভেল এর প্রথম নোড তাই আন্সার ভেক্টরে পুশ করে দেওয়া হচ্ছে।
            frq[level] = true;        // পুশ করে দেওয়ার পর এই লেভেল এর মান এরেতে ট্রু করে দেওয়া হচ্ছে।
        }

        if (node->left)          // যদি নোডের লেফট চাইল্ড থাকে তাহলে 
            q.push({node->left, level + 1});      // কিউ তে পুশ করা হচ্ছে লেফট চাইল্ড এবং তার লেভেল হিসেবে বর্তমান লেভেল থেকে ১ বাড়িয়ে দেওয়া হচ্ছে।
        if (node->right)         // যদি নোডের রাইট চাইল্ড থাকে তাহলে
            q.push({node->right, level + 1});      // কিউ তে পুশ করা হচ্ছে রাইট চাইল্ড এবং তার লেভেল হিসেবে বর্তমান লেভেল থেকে ১ বাড়িয়ে দেওয়া হচ্ছে।
    }
    return v;        // আন্সার ভেক্টর রিটার্ন করা হচ্ছে।
}