Computer >> Máy Tính >  >> Lập trình >> C ++

Cây con được đảo ngược trong C ++

Giả sử chúng ta có hai cây nhị phân được gọi là nguồn và đích; chúng ta phải kiểm tra xem có sự đảo ngược T nào đó của nguồn để nó là cây con của đích hay không. Vì vậy, điều đó có nghĩa là có một nút trong đích giống hệt nhau về giá trị và cấu trúc như T bao gồm tất cả các nút con của nó.

Như chúng ta biết, một cây được cho là sự nghịch đảo của một cây khác nếu -

  • Cả hai cây đều trống rỗng

  • Các cây con bên trái và bên phải của nó được hoán đổi tùy ý và các cây con bên trái và bên phải của nó là nghịch đảo.

Vì vậy, nếu đầu vào giống như nguồn

Cây con được đảo ngược trong C ++

Mục tiêu

Cây con được đảo ngược trong C ++

thì đầu ra sẽ là True

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một kiểm tra hàm (), điều này sẽ lấy node1, node2,

  • nếu node1 và node2 đều là null thì -

    • trả về true

  • nếu node1 hoặc node2 bất kỳ một trong số chúng là null, thì -

    • trả về false

  • nếu val của node1 không bằng val của node2 thì -

    • trả về false

  • op1:=kiểm tra (bên trái của nút1, bên trái của nút2) và kiểm tra (bên phải của nút1, bên phải của nút2)

  • op2:=kiểm tra (bên phải của nút1, bên trái của nút2) và kiểm tra (bên trái của nút1, bên phải của nút2)

  • trả về true khi ít nhất một trong op1 và op2 là true

  • Xác định một hàm giải quyết (), hàm này sẽ lấy nguồn, đích,

  • nếu nguồn và đích trống, thì -

    • trả về true

  • nếu nguồn hoặc đích bất kỳ một trong số chúng là null, thì -

    • trả về false

  • op1:=check (target, source)

  • nếu op1 là true, thì -

    • trả về true

  • trả về true khi ít nhất một trong các giải pháp (nguồn, bên trái mục tiêu) hoặc giải quyết (nguồn, bên phải mục tiêu) là đúng

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

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

Đầu vào 

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

Đầu ra 

1