C++で同等の二分木を反転する

二分木があるとします。二分木を反転する必要があります。フリップは次のことを示します。任意のノードを選択し、左右の子サブツリーを交換します。ここで、バイナリツリーXは、いくつかのフリップ操作の後でXからYを作成できる場合に限り、バイナリツリーYとフリップ同等になります。 2つの二分木がフリップ等価であるかどうかを判断するメソッドを作成する必要があります。ツリーはルートノードroot1とroot2によって与えられます。したがって、木が-

次に、値1、3、および5のノードを反転すると、出力はtrueになります。

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

• 1つの再帰関数solve（）を定義します。これには、2つのツリーt1とt2が必要です。

• root1とroot2がnullの場合、trueを返します

• それ以外の場合、root1がnullまたはroot2がnullの場合、falseを返します

• それ以外の場合、（t1とt2の両方に左側のサブツリーがない）または（t1とt2の両方に左側のサブツリーがあり、これら2つのノードの左側のサブツリーの値が同じである）場合、

  • 戻り値solve（root1の左側、root2の左側）およびsolve（root1の右側、root2の右側）

• それ以外の場合

  • 戻り値solve（root1の左側、root2の右側）およびsolve（root1の右側、root2の左側）

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

例

#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 flipEquiv(TreeNode* root1, TreeNode* root2) {
      if(!root1 && !root2)return true;
      else if(!root1 || !root2)return false;
      else if(root1->val != root2->val) return false;
      else if((!root1->left && !root2->left) || (root1->left && root2->left && root1->left->val ==          root2-      >left->val)){
         return flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right);
      }else{
         return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left);
      }
   }
};
main(){
   vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8};
   TreeNode *r1 = make_tree(v);
   vector<int> v1 = {1,3,2,NULL,6,4,5,NULL,NULL,NULL,NULL,NULL,NULL,8,7};
   TreeNode *r2 = make_tree(v);
   Solution ob;
   cout << (ob.flipEquiv(r1, r2));
}

入力

[1,2,3,4,5,6,null,null,null,7,8]
[1,3,2,null,6,4,5,null,null,null,null,8,7]

出力

1