이진 트리가 주어졌을 때, 아래 조건을 만족하면 해당 트리를 유효한(valid) 이진 트리라고 판단할 수 있습니다.
- 모든 노드의 데이터 값은 왼쪽 자식과 오른쪽 자식 값의 합과 같아야 합니다.
- 어느 한쪽에 자식 노드가 없다면, 그 값은 0으로 간주합니다.
예를 들어 아래와 같은 트리는 위 속성을 만족하는 유효한 이진 트리입니다.
접근 방법
이 속성을 확인하는 특별한 트릭은 없으며, 트리를 재귀적으로 순회해야 합니다. 각 노드에서 현재 노드의 값이 두 자식 노드 값의 합과 일치하는지 검사하고, 모든 노드가 조건을 만족하면 true를, 하나라도 만족하지 않으면 false를 반환합니다.
알고리즘 단계
- 노드가 NULL이거나 리프 노드(자식이 없는 노드)라면 true를 반환합니다. 리프 노드는 자식이 없으므로 항상 조건을 만족하기 때문입니다.
- 왼쪽 자식이 존재하면 그 값을, 오른쪽 자식이 존재하면 그 값을 가져옵니다. 없으면 0으로 둡니다.
- 현재 노드의 값이 왼쪽 자식 값 + 오른쪽 자식 값과 같고, 왼쪽 서브트리와 오른쪽 서브트리도 모두 같은 속성을 만족하는지 재귀적으로 확인합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
bool isValidBinaryTree(node* nd) {
int left_data = 0, right_data = 0;
if(nd == NULL || (nd->left == NULL && nd->right == NULL))
return 1;
else{
if(nd->left != NULL)
left_data = nd->left->data;
if(nd->right != NULL)
right_data = nd->right->data;
if((nd->data == left_data + right_data)&& isValidBinaryTree(nd->left) && isValidBinaryTree(nd->right))
return true;
else
return false;
}
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
node *root = getNode(10);
root->left = getNode(8);
root->right = getNode(2);
root->left->left = getNode(3);
root->left->right = getNode(5);
root->right->right = getNode(2);
if(isValidBinaryTree(root))
cout << "The tree satisfies the children sum property ";
else
cout << "The tree does not satisfy the children sum property ";
}실행 결과
The tree satisfies the children sum property
코드 설명
위 예제에서 루트 노드의 값은 10이며, 왼쪽 자식(8)과 오른쪽 자식(2)의 합인 10과 일치합니다. 마찬가지로 값이 8인 노드는 자식 노드 3과 5의 합과 같고, 값이 2인 노드도 자식 노드 2의 값과 일치합니다. 따라서 프로그램은 트리가 자식 합 속성을 만족한다는 메시지를 출력합니다.
시간 복잡도
이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 전체 노드 수입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 최악의 경우 편향된 트리일 때 O(n), 균형 잡힌 트리일 때 O(log n)입니다.