이 글에서는 주어진 이진 트리가 합 트리(Sum Tree)인지 판별하는 방법을 알아보겠습니다. 먼저 합 트리가 무엇인지부터 정리해 보겠습니다.
합 트리(Sum Tree)란?
합 트리는 각 노드가 자신의 왼쪽 자식과 오른쪽 자식 노드 값의 합을 저장하는 이진 트리입니다. 이 규칙이 모든 노드에 적용되기 때문에, 결과적으로 루트 노드에는 트리 전체 요소들의 총합이 담기게 됩니다. 다음은 합 트리의 대표적인 예시입니다.
판별 방법
합 트리 여부를 확인하는 가장 직관적인 방법은 다음과 같습니다.
1. 각 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리에 속한 모든 노드 값의 합을 각각 구합니다.
2. 두 합을 더한 값이 현재 노드의 값과 일치하는지 비교합니다.
3. 일치하면 합 트리의 조건을 만족하며, 이 검사를 재귀적으로 모든 노드에 적용합니다.
여기서 한 가지 유의할 점은, NULL 노드와 리프 노드는 조건을 검사할 대상이 아니므로 기본적으로 합 트리로 간주한다는 것입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node* left, *right;
};
int sum_of_nodes(node *root) {
if(root == NULL)
return 0;
return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right);
}
int isSumTree(node* node) {
int left_sum, right_sum;
if(node == NULL || (node->left == NULL && node->right == NULL))
return 1;
left_sum = sum_of_nodes(node->left);
right_sum = sum_of_nodes(node->right);
if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))
return 1;
return 0;
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(26);
root->left = getNode(10);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(6);
root->right->right = getNode(3);
if(isSumTree(root))
cout << "The tree is Sum Tree";
else
cout << "The tree is not a Sum Tree";
}출력 결과
The tree is Sum Tree
코드 설명 및 복잡도 분석
위 코드에서 sum_of_nodes() 함수는 특정 노드를 루트로 하는 서브트리 전체의 합을 재귀적으로 계산합니다. isSumTree() 함수는 각 노드에서 왼쪽과 오른쪽 서브트리의 합을 구해 자신의 값과 비교하고, 동시에 양쪽 서브트리 역시 합 트리인지 재귀적으로 확인합니다.
예제 트리의 경우 루트 값 26은 왼쪽 서브트리의 합(4 + 6 + 10 = 20)과 오른쪽 서브트리의 합(3 + 3 = 6)을 더한 값과 정확히 일치하므로, 이 트리는 합 트리임이 확인됩니다.
이 방식은 각 노드마다 서브트리의 합을 새로 계산하므로 최악의 경우 시간 복잡도는 O(n²)입니다. 만약 성능이 중요하다면, 하위 노드부터 합을 반환하며 한 번의 순회(O(n))만으로 판별하는 후위 순회(post-order) 기반 최적화 기법을 사용하는 것이 좋습니다.