ค้นหาโหนดที่สอดคล้องกันของต้นไม้ไบนารีในโคลนของต้นไม้นั้นใน C++

สมมติว่าเรามีต้นไม้ไบนารีสองต้นที่เป็นต้นฉบับและลอกแบบแล้ว และได้รับการอ้างอิงไปยังเป้าหมายของโหนดในทรีดั้งเดิม ต้นไม้โคลนเป็นสำเนาของต้นไม้ดั้งเดิม เราต้องหาการอ้างอิงไปยังโหนดเดียวกันในทรีที่ลอกแบบมา

ดังนั้นหากต้นไม้อยู่ด้านล่างและเป้าหมายคือ 3 ผลลัพธ์จะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า Solve() ซึ่งจะใช้ node1m node2 และเป้าหมาย

• ถ้า node1 เป็นโมฆะ ให้คืนค่า null

• ถ้า node1 เป็นเป้าหมาย และค่าของ node 1 เป็นค่าของ node2 ให้คืนค่า node2

• leftPart :=แก้ (ซ้ายของ node1, ซ้ายของ node2, เป้าหมาย)

• rightPart :=แก้ (ด้านขวาของโหนด1, ด้านขวาของโหนด2, เป้าหมาย)

• ส่งคืน leftPart หาก leftPart ไม่ใช่ null มิฉะนั้น rightPart

• จากเมธอดหลัก call return Solve (ดั้งเดิม, โคลน, เป้าหมาย)

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

3