C++ में डुप्लिकेट उपट्री ढूंढना

मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें सभी डुप्लिकेट उपट्री ढूंढने हैं। इसलिए प्रत्येक प्रकार के डुप्लिकेट उपट्री के लिए, हमें उनमें से किसी एक का रूट नोड लौटाना है। मान लीजिए हमारे पास ऐसा ट्री है:

डुप्लिकेट उपट्री हैं:

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

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक सरणी ret बनाएं, एक मैप m बनाएं
• एक पुनरावर्ती विधि solve() परिभाषित करें। यह नोड को इनपुट के रूप में लेगा। यह इस प्रकार काम करता है:
  • यदि नोड null है, तो "-1" लौटाएं
  • x := नोड का मान स्ट्रिंग के रूप में, फिर इसके साथ "#" जोड़ें।
  • left := solve(नोड के बाएं), right := solve(नोड के दाएं)
  • x := x + "#" + left + "#" + right
  • m[x] को 1 से बढ़ाएं
  • यदि m[x] == 2, तो नोड को ret में डालें
  • x लौटाएं
• मुख्य विधि से solve(root) कॉल करें और ret लौटाएं

उदाहरण

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

class TreeNode{ 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data){ 
        val = data; 
        left = 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; 
} 

void tree_level_trav(TreeNode* root){ 
    if (root == NULL) return; 
    cout << "["; 
    queue<TreeNode *> q; 
    TreeNode *curr; 
    q.push(root); 
    q.push(NULL); 
    while (q.size() > 1) { 
        curr = q.front(); 
        q.pop(); 
        if (curr == NULL){ 
            q.push(NULL); 
        } else { 
            if(curr->left) q.push(curr->left); 
            if(curr->right) q.push(curr->right); 
            if(curr->val == 0 || curr == NULL){ 
                cout << "null" << ", "; 
            } else { 
                cout << curr->val << ", "; 
            } 
        } 
    } 
    cout << "]" << endl; 
} 

class Solution { 
public: 
    vector<TreeNode*> ret; 
    map<string, int> m; 
    
    string solve(TreeNode* node){ 
        if(!node || node->val == 0){ 
            return "-1"; 
        } 
        string x = to_string(node->val); 
        x += "#"; 
        string left = solve(node->left); 
        string right = solve(node->right); 
        x = x + "#" + left + "#" + right; 
        m[x]++; 
        if(m[x] == 2){ 
            ret.push_back(node); 
        } 
        return x; 
    } 
    
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { 
        ret.clear(); 
        m.clear(); 
        solve(root); 
        return ret; 
    } 
}; 

int main(){ 
    vector<int> v = {1,2,3,4,NULL,2,4,NULL,NULL,NULL,NULL,4}; 
    Solution ob; 
    TreeNode *root = make_tree(v); 
    vector<TreeNode*> trees = ob.findDuplicateSubtrees(root); 
    for(TreeNode *t : trees){ 
        tree_level_trav(t); 
    } 
}

इनपुट

[1,2,3,4,null,2,4,null,null,null,null,4]

आउटपुट

[4, ] [2, 4, ]