C++ में उलटा सबट्री

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

जैसा कि हम जानते हैं कि एक पेड़ को दूसरे पेड़ का उलटा कहा जाता है यदि या तो -

• दोनों पेड़ खाली हैं

• इसके बाएँ और दाएँ बच्चे वैकल्पिक रूप से अदला-बदली किए जाते हैं और इसके बाएँ और दाएँ उपप्रकार व्युत्क्रम होते हैं।

तो, अगर इनपुट स्रोत की तरह है

लक्ष्य

तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन चेक () को परिभाषित करें, इसमें नोड 1, नोड 2,

  लगेगा

• यदि नोड1 और नोड2 दोनों शून्य हैं, तो -

  • सही लौटें

• यदि नोड1 या नोड2 उनमें से कोई एक रिक्त है, तो -

  • झूठी वापसी

• यदि नोड1 का मान नोड2 के मान के बराबर नहीं है, तो -

  • झूठी वापसी

• op1:=चेक (नोड 1 के बाएं, नोड 2 के बाएं) और चेक (नोड 1 के दाएं, नोड 2 के दाएं)

• op2:=चेक (नोड 1 के दाएं, नोड 2 के बाएं) और चेक (नोड 1 के बाएं, नोड 2 के दाएं)

• जब op1 और op2 में से कम से कम एक सत्य हो तो सही लौटें

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह स्रोत, लक्ष्य लेगा,

• अगर स्रोत और लक्ष्य खाली हैं, तो -

  • सही लौटें

• यदि स्रोत या लक्ष्य उनमें से कोई एक शून्य है, तो -

  • झूठी वापसी

• op1:=चेक (लक्ष्य, स्रोत)

• यदि op1 सत्य है, तो -

  • सही लौटें

• जब हल (स्रोत, लक्ष्य के बाएँ) या हल (स्रोत, लक्ष्य का दायाँ) में से कम से कम एक सही हो तो सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      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);
   }
};
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));
}

इनपुट

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);

आउटपुट

1