이번 글에서는 주어진 이진 트리를 논리 AND(Logical AND) 속성을 만족하는 트리로 변환하는 방법을 C++ 코드와 함께 살펴보겠습니다.
여기서 논리 AND 속성이란, 트리의 모든 내부 노드가 자신의 값으로 두 자식 노드 값의 AND 연산 결과를 갖는다는 의미입니다. 예를 들어 왼쪽 자식이 1이고 오른쪽 자식이 0이라면, 부모 노드의 값은 1 AND 0 = 0이 됩니다. 단, 모든 노드의 값은 0 또는 1로 제한됩니다.
문제 해결 접근 방식
이 문제는 후위 순회(Post-order Traversal)를 사용하면 깔끔하게 해결할 수 있습니다. 후위 순회는 '왼쪽 서브트리 → 오른쪽 서브트리 → 루트' 순서로 노드를 방문하기 때문에, 자식 노드들의 값이 먼저 확정된 뒤에 부모 노드의 값을 계산할 수 있습니다.
알고리즘의 동작 순서는 다음과 같습니다.
- 현재 노드가 NULL이면 아무 작업 없이 반환합니다.
- 왼쪽 서브트리를 재귀적으로 변환합니다.
- 오른쪽 서브트리를 재귀적으로 변환합니다.
- 양쪽 자식이 모두 존재하는 경우, 현재 노드의 값을 두 자식 값의 비트 AND(&) 연산 결과로 갱신합니다.
리프 노드는 자식이 없기 때문에 값이 변경되지 않고 그대로 유지됩니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 이진 트리의 노드 구조체
struct Node{
int data;
struct Node* left;
struct Node* right;
};
// 새로운 노드 생성 함수
struct Node* newNode(int key){
struct Node* node = new Node;
node->data= key;
node->left = node->right = NULL;
return node;
}
// 논리 AND 속성을 만족하도록 트리를 변환하는 함수
void transform_tree(Node *root){
if (root == NULL)
return;
// 왼쪽 서브트리를 먼저 처리
transform_tree(root->left);
// 오른쪽 서브트리 처리
transform_tree(root->right);
// 양쪽 자식이 모두 있으면 현재 노드의 값을 AND 연산 결과로 갱신
if (root->left != NULL && root->right != NULL)
root->data = (root->left->data) & (root->right->data);
}
// 중위 순회 결과 출력
void print_tree(Node* root){
if (root == NULL)
return;
print_tree(root->left);
printf("%d ", root->data);
print_tree(root->right);
}
int main(){
Node *root=newNode(0);
root->left=newNode(1);
root->right=newNode(0);
root->left->left=newNode(0);
root->left->right=newNode(1);
root->right->left=newNode(1);
root->right->right=newNode(1);
printf("변환 전 :\n");
print_tree(root);
transform_tree(root);
printf("\n변환 후 :\n");
print_tree(root);
return 0;
}실행 결과
변환 전 : 0 1 1 0 1 0 1 변환 후 : 0 0 1 0 1 1 1
결과 분석
변환 전 트리의 중위 순회 결과는 0 1 1 0 1 0 1입니다. 변환이 완료되면 루트 노드는 왼쪽 자식(1)과 오른쪽 자식(0)의 AND인 0이 되고, 왼쪽 내부 노드는 0 AND 1 = 0, 오른쪽 내부 노드는 1 AND 1 = 1로 갱신됩니다. 그 결과 중위 순회 값이 0 0 1 0 1 1 1로 바뀌게 됩니다.
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되므로, 트리의 높이를 h라 할 때 O(h)입니다.