문제 개요
이 튜토리얼에서는 이진 트리(binary tree)를 변환하여 모든 노드가 자신의 오른쪽 서브트리(subtree)에 있는 모든 노드 값의 합을 저장하도록 만드는 프로그램을 다룹니다.
즉, 하나의 이진 트리가 주어졌을 때, 각 노드의 값이 "노드 자신의 원래 값 + 오른쪽 서브트리 전체의 합"이 되도록 갱신된 새로운 트리를 만드는 것이 목표입니다.
접근 방식
이 문제는 재귀 호출을 활용한 후위 순회(post-order traversal)로 깔끔하게 해결할 수 있습니다. 동작 과정은 다음과 같습니다.
- 루트 노드에서 시작해 트리를 재귀적으로 탐색합니다.
- 각 노드에서 오른쪽 서브트리의 합과 왼쪽 서브트리의 합을 먼저 구합니다.
- 현재 노드의 데이터에 오른쪽 서브트리의 합을 더해 값을 갱신합니다.
- 상위 호출에서 사용할 수 있도록 "갱신된 현재 노드의 값 + 왼쪽 서브트리의 합"을 반환합니다.
이 과정을 거치면 리프 노드는 자기 자신의 값을 그대로 유지하고, 내부 노드는 자신과 오른쪽 자손 노드들의 합을 저장하게 됩니다. 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 트리 노드 구조체
struct Node {
int data;
Node *left, *right;
};
// 새 노드 생성
struct Node* createNode(int item){
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// 오른쪽 서브트리 합을 반영한 새 이진 트리 생성
int rightsum_tree(Node* root){
if (!root)
return 0;
if (root->left == NULL && root->right == NULL)
return root->data;
// 왼쪽/오른쪽 서브트리의 값 갱신
int rightsum = rightsum_tree(root->right);
int leftsum = rightsum_tree(root->left);
// 오른쪽 서브트리의 합을 현재 노드에 더함
root->data += rightsum;
return root->data + leftsum;
}
// 중위 순회로 트리 출력
void inorder(struct Node* node){
if (node == NULL)
return;
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
int main(){
struct Node* root = NULL;
root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->right = createNode(6);
rightsum_tree(root);
cout << "Updated Binary Tree :\n";
inorder(root);
return 0;
}
실행 결과
Updated Binary Tree : 4 7 5 10 9 6
결과 분석
예제 트리는 루트 1, 왼쪽 자식 2(자식으로 4와 5), 오른쪽 자식 3(오른쪽 자식 6)으로 구성되어 있습니다. 변환 후 중위 순회(inorder) 결과를 노드별로 살펴보면 다음과 같습니다.
- 4, 5, 6: 리프 노드이므로 원래 값을 그대로 유지합니다.
- 7: 노드 2의 값(2) + 오른쪽 자식 5의 값(5)
- 9: 노드 3의 값(3) + 오른쪽 자식 6의 값(6)
- 10: 루트 1의 값(1) + 오른쪽 서브트리 전체의 합(3 + 6 = 9)
이처럼 모든 노드가 "자신의 값 + 오른쪽 서브트리의 합"을 저장하도록 트리가 성공적으로 변환되었음을 확인할 수 있습니다.