C++에서 해당 트리의 클론에서 이진 트리의 해당 노드 찾기

원본 및 복제된 두 개의 이진 트리가 있고 원본 트리의 노드 대상에 대한 참조가 제공된다고 가정합니다. 복제된 트리는 실제로 원본 트리의 복사본입니다. 복제된 트리에서 동일한 노드에 대한 참조를 찾아야 합니다.

따라서 트리가 아래와 같고 대상이 3이면 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve()라는 메서드를 정의하면 node1m node2와 target

  이 사용됩니다.

• node1이 null이면 null을 반환합니다.

• node1이 target이고 node1의 값이 node2의 값이면 node2를 반환합니다.

• leftPart :=solve(node1의 왼쪽, node2의 왼쪽, target)

• rightPart :=solve(node1 오른쪽, node2 오른쪽, target)

• leftPart가 null이 아니면 leftPart 반환, 그렇지 않으면 rightPart

• 기본 메소드 호출에서 solve(original, cloned, target)

예시(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