Tìm một nút tương ứng của cây nhị phân trong bản sao của cây đó trong C ++

Giả sử chúng ta có hai cây nhị phân ban đầu và được sao chép và được cung cấp một tham chiếu đến đích nút trong cây ban đầu. Cây nhân bản thực chất là một bản sao của cây gốc. Chúng ta phải tìm một tham chiếu đến cùng một nút trong cây nhân bản.

Vì vậy, nếu cây giống như bên dưới và mục tiêu là 3, thì đầu ra sẽ là 3.

Để 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 phương thức có tên là giải quyết (), phương thức này sẽ lấy node1m node2 và target

• nếu node1 là null, thì trả về null

• nếu node1 là đích và giá trị của node 1 là giá trị của node2, thì trả về node2

• leftPart:=giải quyết (bên trái của nút1, bên trái của nút2, mục tiêu)

• rightPart:=giải quyết (bên phải của node1, bên phải của node2, target)

• trả về leftPart, nếu leftPart không null, nếu không thì rightPart

• Từ phương thức chính, cuộc gọi trả về giải quyết (gốc, sao chép, đích)

Ví dụ (C ++)

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

#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;
}
class Solution {
   public:
   TreeNode* solve(TreeNode* node1, TreeNode* node2, TreeNode*
   target){
      if(!node1) return NULL;
      if(node1 == target && node1->val == node2->val) return node2;
      TreeNode* leftPart = solve(node1->left, node2->left, target);
      TreeNode* rightPart = solve(node1->right, node2->right, target);
      return leftPart? leftPart : rightPart;
   }
   TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned,
   TreeNode* target) {
      return solve(original, cloned, target);
   }
};
main(){
   vector<int> v = {7,4,3,NULL,NULL,6,19};
   TreeNode *root = make_tree(v);
   TreeNode *cloned = make_tree(v);
   TreeNode *target = root->right; //The node with value 3
   Solution ob;
   cout << (ob.getTargetCopy(root, cloned, target))->val;
}

Đầu vào

[7,4,3,null,null,6,19]
3

Đầu ra

3