C++-এ Contaminated Binary Tree-এ এলিমেন্ট খুঁজে বের করা

ধরি আমাদের একটি বাইনারি ট্রি আছে। সেই ট্রির নিয়মগুলো নিচের মত:

• root.val == 0

• যদি treeNode.val হল x এবং treeNode.left null না হয়, তবে treeNode.left.val = 2 * x + 1

• যদি treeNode.val হল x এবং treeNode.right null না হয়, তবে treeNode.right.val = 2 * x + 2

এখন যেহেতু বাইনারি ট্রিটি contaminated (দূষিত)। এর মানে হল ট্রি নোডের সব val -1-এ চেঞ্জ করা হয়েছে। আমাদের প্রথমে বাইনারি ট্রিটি রিকভার করতে হবে এবং তারপর FindElements ক্লাস ইমপ্লিমেন্ট করতে হবে নিচের মত:

• FindElements(TreeNode* root) দূষিত বাইনারি ট্রি দিয়ে অবজেক্ট ইনিশিয়ালাইজ করে, আমাদের আগে সেটা রিকভার করতে হবে।

• bool find(int target)। এটি রিটার্ন করবে টার্গেট ভ্যালু রিকভার করা বাইনারি ট্রিতে আছে কিনা।

ট্রি যদি নিচের মত হয়:

রিকভার করার পর যদি ১, ৩ এবং ৫ খুঁজি, তবে রেজাল্ট হবে true, true এবং false।

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

• একটি সেট a ডিফাইন করুন

• একটি dfs() মেথড ডিফাইন করুন, এটি root এবং rootVal নিবে। rootVal początovala -1

• যদি root null হয়, তবে রিটার্ন করুন

• যদি rootVal -1 হয়, তবে root-এর ভ্যালু 0 সেট করুন, অন্যথায় rootVal সেট করুন

• root-এর ভ্যালু a-তে ইনসার্ট করুন

• dfs(left of root, 2* value of root + 1), dfs(right of root, 2* value of root + 2) কল করুন

• ইনিশিয়ালাইজেশন (রিকনস্ট্রাকশন) এর জন্য, dfs(root, -1) কল করুন

• কোনো এলিমেন্ট খুঁজতে, চেক করুন এলিমেন্টটি a-তে আছে কিনা, থাকলে true রিটার্ন করুন, অন্যথায় false

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:

উদাহরণ

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

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

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left) {
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right) {
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) {
        insert(&root, v[i]);
    }
    return root;
}

class FindElements {
public:
    set<int> a;
    void dfs(TreeNode* root, int rootVal = -1) {
        if(!root) return;
        root->val = rootVal == -1 ? 0 : rootVal;
        a.insert(root->val);
        dfs(root->left, 2*root->val + 1);
        dfs(root->right, 2*root->val + 2);
    }
    FindElements(TreeNode* root) {
        dfs(root);
    }
    bool find(int t) {
        return a.find(t) != a.end();
    }
};

int main() {
    vector<int> v = {-1,-1,-1,-1,-1};
    TreeNode *root = make_tree(v);
    FindElements ob(root);
    cout << (ob.find(1)) << endl;
    cout << (ob.find(3)) << endl;
    cout << (ob.find(5)) << endl;
}

ইনপুট

ট্রি [-1,-1,-1,-1,-1] দিয়ে ইনিশিয়ালাইজ করুন, তারপর find(1), find(3) এবং find(5) কল করুন

আউটপুট

1 1 0