Tìm các cây con trùng lặp trong C ++

Giả sử chúng ta có một cây nhị phân. Chúng tôi phải tìm tất cả các cây con trùng lặp. Vì vậy, đối với mỗi loại cây con trùng lặp, chúng ta phải trả về nút gốc của bất kỳ cây con nào trong số chúng. Vì vậy, giả sử chúng ta có một cái cây giống như -

Các cây con trùng lặp là -

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

• Tạo mảng ret, tạo bản đồ m
• Định nghĩa một phương thức đệ quy giải quyết (). Điều này sẽ lấy nút làm đầu vào. Điều này hoạt động như -
• nếu nút là null, thì trả về -1
• x:=giá trị của nút dưới dạng chuỗi, sau đó nối “#” với nó.
• left:=giải quyết (bên trái của nút), bên phải:=giải quyết (bên phải của nút)
• x:=x nối ​​“#” nối trái, nối “#” nối phải
• tăng m [x] lên 1
• nếu m [x] là 2, thì hãy chèn nút vào ret
• trả về x
• Từ phương thức chính, hãy gọi giải quyết (root) và trả về ret

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 = 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;
         }
         void tree_level_trav(TreeNode*root){
            if (root == NULL) return;
            cout << "[";
            queue<TreeNode *> q;
            TreeNode *curr;
            q.push(root);
            q.push(NULL);
            while (q.size() > 1) {
               curr = q.front();
               q.pop();
               if (curr == NULL){
                  q.push(NULL);
            } else {
            if(curr->left)
            q.push(curr->left);
            if(curr->right)
            q.push(curr->right);
         if(curr->val == 0 || curr == NULL){
               cout << "null" << ", ";
         } else {
               cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
  vector <TreeNode*> ret;
   map <string, int> m;
   string solve(TreeNode* node){
      if(!node || node->val == 0){
         return "-1";
      }
      string x = to_string(node->val);
      x += "#";
      string left = solve(node->left);
      string right = solve(node->right);
      x = x + "#" + left + "#" + right;
      m[x]++;
      if(m[x] == 2){
         ret.push_back(node);
      }
      return x;
   }
   vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
      ret.clear();
      m.clear();
      solve(root);
      return ret;
   }
};
main(){
   vector<int> v = {1,2,3,4,NULL,2,4,NULL,NULL,NULL,NULL,4};
   Solution ob;
   TreeNode *root = make_tree(v);
   vector<TreeNode*> trees = ob.findDuplicateSubtrees(root);
   for(TreeNode *t : trees){
      tree_level_trav(t);
   }
}

Đầu vào

[1,2,3,4,null,2,4,null,null,null,null,4]

Đầu ra

[4, ]
[2, 4, ]