원본(original)과 복제본(cloned)이라는 두 개의 이진 트리가 있고, 원본 트리 내 특정 노드인 target에 대한 참조가 주어졌다고 가정해 봅시다. 복제된 트리는 원본 트리와 구조 및 값이 완전히 동일한 복사본입니다. 이때 우리가 해야 할 작업은 복제된 트리에서 원본의 target 노드와 동일한 위치에 있는 노드의 참조를 찾아 반환하는 것입니다.
예를 들어 아래와 같은 트리에서 target이 값 3을 가진 노드라면, 출력 결과 역시 3이 됩니다.
문제 해결 접근 방법
두 트리의 구조가 완전히 동일하기 때문에, 원본 트리와 복제 트리를 동시에 순회하면 됩니다. 순회 중 원본 트리에서 target 노드에 도달하는 순간, 복제 트리에서의 현재 위치가 바로 찾고자 하는 노드입니다. 재귀(DFS) 방식으로 다음 단계를 따릅니다.
- solve()라는 메서드를 정의합니다. 이 메서드는 node1(원본 트리의 현재 노드), 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; //값이 3인 노드
Solution ob;
cout << (ob.getTargetCopy(root, cloned, target))->val;
}입력
[7,4,3,null,null,6,19] 3
출력
3
알고리즘 설명
위 코드는 원본 트리와 복제 트리를 루트부터 깊이 우선 탐색(DFS)으로 동시에 내려갑니다. 각 재귀 호출에서 원본 트리의 현재 노드가 target과 포인터 수준에서 일치하는지 확인하고, 일치한다면 복제 트리의 같은 위치에 있는 노드를 즉시 반환합니다. 왼쪽 서브트리에서 결과를 찾지 못하면 오른쪽 서브트리를 계속 탐색하며, 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N), 재귀 호출 스택에 의한 공간 복잡도 역시 최악의 경우 O(N)입니다.