문제 개요
두 개의 이진 트리가 주어졌다고 가정해 봅시다. 한 트리를 다른 트리 위에 겹쳐 놓으면 일부 노드는 서로 겹치고, 나머지 노드는 겹치지 않습니다. 이때 두 트리를 새로운 이진 트리 하나로 병합해야 합니다.
병합 규칙은 다음과 같습니다.
- 두 노드가 겹치는 경우: 두 노드의 값을 더한 값이 병합된 노드의 새로운 값이 됩니다.
- 한쪽 노드만 존재하는 경우: 값이 있는(비어 있지 않은) 노드가 그대로 새 트리의 노드로 사용됩니다.
예를 들어 입력 트리가 다음과 같다면,
트리 1: 1 트리 2: 2
/ \ / \
3 2 1 3
/ \ \
5 4 7병합 결과는 다음과 같습니다.
병합된 트리: 3
/ \
4 5
/ \ \
5 4 7해결 접근 방식
이 문제는 재귀적으로 간단하게 해결할 수 있습니다. 두 트리의 노드 n1과 n2를 인자로 받는 solve() 메서드를 다음 순서로 구현합니다.
- n1이 NULL이고 n2가 존재하면 n2를 반환합니다. 반대로 n2가 NULL이고 n1이 존재하면 n1을 반환하며, 둘 다 NULL이면 NULL을 반환합니다.
- 두 노드가 모두 존재하면 n1의 값에 n2의 값을 더합니다. 즉, n1->val := n1->val + n2->val
- n1의 왼쪽 자식 := solve(n1의 왼쪽 자식, n2의 왼쪽 자식)
- n1의 오른쪽 자식 := solve(n1의 오른쪽 자식, n2의 오른쪽 자식)
- n1을 반환합니다.
이 방식은 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다. 여기서 N은 두 트리 중 더 많은 노드를 가진 트리의 노드 수입니다.
구현 예제
아래 C++ 코드를 통해 실제 동작을 확인해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v){
val = v;
left = right = NULL;
}
};
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(TreeNode* n1, TreeNode* n2) {
if(!n1 && n2)
return n2;
else if(!n2 && n1)
return n1;
else if(!n1 && !n2)
return NULL;
n1->val+=n2->val;
n1->left = solve(n1->left,n2->left);
n1->right = solve(n1->right,n2->right);
return n1;
}
};
main(){
TreeNode *root1 = new TreeNode(1);
root1->left = new TreeNode(3);
root1->right = new TreeNode(2);
root1->left->left = new TreeNode(5);
TreeNode *root2 = new TreeNode(2);
root2->left = new TreeNode(1);
root2->right = new TreeNode(3);
root2->left->right = new TreeNode(4);
root2->right->right = new TreeNode(7);
Solution ob;
TreeNode *root_res = ob.solve(root1, root2);
inord(root_res);
}입력
TreeNode *root1 = new TreeNode(1); root1->left = new TreeNode(3); root1->right = new TreeNode(2); root1->left->left = new TreeNode(5); TreeNode *root2 = new TreeNode(2); root2->left = new TreeNode(1); root2->right = new TreeNode(3); root2->left->right = new TreeNode(4); root2->right->right = new TreeNode(7);
출력
5 4 4 3 5 7
출력은 병합된 트리를 중위 순회(inorder traversal)한 결과입니다. 왼쪽 서브트리(5, 4, 4), 루트(3), 오른쪽 서브트리(5, 7) 순서로 방문하여 정확히 기대한 결과가 출력되는 것을 확인할 수 있습니다.