বাইনারি ট্রি থেকে দূরত্ব K-তে নোডগুলো খুঁজে বের করা C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রি, একটি টার্গেট নোড এবং একটি মান K দেওয়া আছে। টার্গেট নোড থেকে দূরত্ব K-তে থাকা সব নোডের ভ্যালু লিস্ট আকারে রিটার্ন করতে হবে। দূরত্ব মানে এজ সংখ্যা।

উদাহরণ

রুট = [3,5,1,6,2,0,8,null,null,7,4], টার্গেট = ৫, K = ২

আউটপুট: [7,4,1] — কারণ ৭, ৪ এবং ১ টার্গেট নোড ৫ থেকে দূরত্ব ২-তে আছে।

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

1. DFS দিয়ে প্যারেন্ট ম্যাপ তৈরি করুন: প্রতিটি নোডের প্যারেন্ট স্টোর করুন যেন উপরের দিকে যাওয়া যায়।
2. টার্গেট নোড থেকে BFS চালান:
   • কিউতে {node, level} পুশ করুন।
   • ভিজিটেড সেট রেখে একবারই ভিজিট করুন।
   • যখন level == K হয়, নোডের ভ্যালু আন্সারে যোগ করুন।
   • বাম চাইল্ড, ডান চাইল্ড ও প্যারেন্ট — তিনদিকেই যান (যদি ভিজিটেড না হয় এবং লেভেল K-এর চেয়ে কম হয়)।

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:
    unordered_map<TreeNode*, TreeNode*> parent;

    void dfs(TreeNode* node, TreeNode* pa = nullptr) {
        if (!node) return;
        parent[node] = pa;
        dfs(node->left, node);
        dfs(node->right, node);
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        vector<int> ans;
        parent.clear();
        dfs(root);

        queue<pair<TreeNode*, int>> q;
        q.push({target, 0});
        unordered_set<TreeNode*> visited;
        visited.insert(target);

        while (!q.empty()) {
            auto [node, level] = q.front(); q.pop();
            if (level == k) {
                ans.push_back(node->val);
            }
            if (node->left && level + 1 <= k && !visited.count(node->left)) {
                q.push({node->left, level + 1});
                visited.insert(node->left);
            }
            if (node->right && level + 1 <= k && !visited.count(node->right)) {
                q.push({node->right, level + 1});
                visited.insert(node->right);
            }
            if (parent[node] && level + 1 <= k && !visited.count(parent[node])) {
                q.push({parent[node], level + 1});
                visited.insert(parent[node]);
            }
        }
        return ans;
    }
};

int main() {
    // ট্রি বানান এবং টেস্ট করুন
    return 0;
}

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

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

• সময় জটিলতা: O(N) — N = নোড সংখ্যা। DFS ও BFS দুটোই O(N)।
• স্থান জটিলতা: O(N) — প্যারেন্ট ম্যাপ, কিউ, ভিজিটেড সেট।