C++-এ ইনভার্টেড সাবট্রি (Inverted Subtree) চেক করার প্রোগ্রাম

সমস্যা বিবরণ

দুটি বাইনারি ট্রি source এবং target দেওয়া থাকলে, যাচাই করুন কি source-এর কোনো ইনভার্সন (left-right swap করা যেতে পারে যেকোনো নোডে) target-এর সাবট্রি হিসেবে আছে।

সমাধানের পদ্ধতি (Recursive)

1. check(node1, node2): দুটি ট্রি ইনভার্সন-ইকুইভ্যালেন্ট কিনা চেক করুন।
   • দউটি NULL → true
   • একটি NULL → false
   • ভ্যালু ভিন্ন → false
   • অপশন ১: (left-left && right-right)
   • অপশন ২: (left-right && right-left)
   • রিটার্ন op1 || op2
2. solve(source, target):
   • target-র প্রতিটি নোডে check(target, source) কল করুন।
   • রিকার্সিভলি target-র লেফ্ট ও রাইটে খুঁজুন।

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:
    bool check(TreeNode* node1, TreeNode* node2) {
        if (!node1 && !node2) return true;
        if (!node1 || !node2) return false;
        if (node1->val != node2->val) return false;
        bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
        bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
        return op1 || op2;
    }
    
    bool solve(TreeNode* source, TreeNode* target) {
        if (!target && !source) return true;
        if (!target || !source) return false;
        bool op1 = check(target, source);
        if (op1) return true;
        return solve(source, target->left) || solve(source, target->right);
    }
};

int main() {
    Solution ob;
    TreeNode* target = new TreeNode(6);
    target->left = new TreeNode(3);
    target->right = new TreeNode(1);
    target->right->left = new TreeNode(3);
    target->right->right = new TreeNode(2);
    target->right->right->left = new TreeNode(4);
    
    TreeNode* source = new TreeNode(1);
    source->left = new TreeNode(2);
    source->right = new TreeNode(3);
    source->left->right = new TreeNode(4);
    
    cout << ob.solve(source, target);
    return 0;
}

আউটপুট

1 (True)

জটিলতা

• সময়: O(n × m) — n = target নোড, m = source নোড
• স্থান: O(h) — রিকার্সন স্ট্যাক