C++の反転サブツリー

私たちが知っているように、次のいずれかの場合、ツリーは別のツリーの反転であると言われます-

• 両方の木は空です

• その左と右の子はオプションで交換され、その左と右のサブツリーは反転です。

したがって、入力がソースのようなものである場合

ターゲット

その場合、出力はTrueになります

これを解決するには、次の手順に従います-

• 関数check（）を定義します。これには、node1、node2、

  が必要です。

• node1とnode2の両方がnullの場合、-

  • trueを返す

• node1またはnode2のいずれかがnullの場合、-

  • falseを返す

• node1のvalがnode2のvalと等しくない場合、-

  • falseを返す

• op1：=check（node1の左側、node2の左側）およびcheck（node1の右側、node2の右側）

• op2：=check（node1の右側、node2の左側）およびcheck（node1の左側、node2の右側）

• op1とop2の少なくとも1つがtrueの場合にtrueを返します

• 関数solve（）を定義します。これは、ソース、ターゲット、

  を取ります。

• ソースとターゲットが空の場合、-

  • trueを返す

• ソースまたはターゲットのいずれかがnullの場合、-

  • falseを返す

• op1：=check（target、source）

• op1がtrueの場合、-

  • trueを返す

• 少なくとも1つのsolve（ソース、ターゲットの左側）またはsolve（ソース、ターゲットの右側）がtrueの場合にtrueを返します

理解を深めるために、次の実装を見てみましょう-

例

#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