Lật cây nhị phân tương đương trong C ++

Giả sử chúng ta có một cây nhị phân. Chúng ta phải lật cây nhị phân. Việc lật cho biết:chọn bất kỳ nút nào và hoán đổi các cây con bên trái và bên phải. Bây giờ cây nhị phân X tương đương với cây nhị phân Y nếu và chỉ khi chúng ta có thể tạo Y từ X, sau một số thao tác lật. Chúng ta phải viết một phương thức xác định xem hai cây nhị phân có lật tương đương hay không. Các cây được cung cấp bởi các nút gốc root1 và root2. Vì vậy, nếu cây cối -

Khi đó đầu ra sẽ là true, nếu chúng ta lật các nút có giá trị 1, 3 và 5.

Để 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 hàm đệ quy giải quyết (), điều này sẽ mất hai cây t1 và t2.
nếu root1 và root2 là null, thì trả về true
ngược lại khi root1 là null hoặc root2 là null thì trả về false
ngược lại khi (t1 và t2 đều không có cây con bên trái) hoặc (t1 và t2 đều có cây con bên trái và giá trị của cây con bên trái của hai nút này giống nhau) thì
- trả về giải quyết (bên trái của root1, bên trái của root2) và giải quyết (bên phải của root1, bên phải của root2)
nếu không thì
- trả về giải quyết (bên trái của root1, bên phải của root2) và giải quyết (bên phải của root1, bên trái của root2)

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

Đầu vào

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

Lật cây nhị phân tương đương trong C ++

Ví dụ

Đầu vào

Đầu ra