C++ में सेम ट्री

समस्या विवरण

मान लीजिए हमारे पास दो बाइनरी ट्री हैं; हमें एक फ़ंक्शन परिभाषित करना है जो जांचे कि वे समान हैं या नहीं। हम जानते हैं कि बाइनरी ट्री को समान माना जाता है जब वे संरचनात्मक रूप से समान होते हैं और नोड्स का मान समान होता है।

उदाहरण

यदि इनपुट है: [1,2,3], [1,2,3], तो आउटपुट होगा True

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (रिकर्सिव दृष्टिकोण):

isSameTree नामक एक फ़ंक्शन परिभाषित करें, जो दो ट्री नोड्स p और q लेता है
यदि p, NULL के समान है और q, NULL के समान है:
- true लौटाएं
यदि p, NULL के समान है या q, NULL के समान है:
- false लौटाएं
यदि p का मान, q के मान के समान है और isSameTree(p का लेफ्ट, q का लेफ्ट) true है और isSameTree(p का राइट, q का राइट) true है:
- true लौटाएं
false लौटाएं

C++ कार्यान्वयन

#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 Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode* q) {
        if (p == NULL && q == NULL)
            return true;
        if (p == NULL || q == NULL)
            return false;
        if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
            return true;
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3}, v1 = {1,2,3};
    TreeNode *root1 = make_tree(v);
    TreeNode *root2 = make_tree(v1);
    cout << (ob.isSameTree(root1, root2));
    return 0;
}

इनपुट

{1,2,3}, {1,2,3}