C++로 이진 트리에서 단일 값 하위 트리 개수 구하기

이진 트리가 하나 주어졌다고 가정해 보겠습니다. 우리의 과제는 이 트리 안에 포함된 단일 값 하위 트리(single valued subtree)의 개수를 세는 것입니다. 단일 값 하위 트리란 해당 하위 트리를 구성하는 모든 노드가 동일한 값을 가지는 경우를 의미합니다.

예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.

이 트리에는 총 네 개의 단일 값 하위 트리가 존재하며, 그 구성은 아래와 같습니다.

해결 접근 방식

이 문제는 상향식(bottom-up) 방식으로 효율적으로 해결할 수 있습니다. 재귀적으로 각 하위 트리를 방문할 때, 현재 노드를 루트로 하는 하위 트리가 단일 값이라면 true를 반환하고 카운터를 1 증가시킵니다.

여기서 핵심은 count 변수를 재귀 호출 시 참조(reference) 매개변수로 전달한다는 점입니다. 또한 함수가 반환하는 값은 왼쪽 및 오른쪽 자식 하위 트리가 단일 값인지 여부를 판단하는 데 활용됩니다. 즉, 어느 한쪽이라도 단일 값이 아니라면 부모 노드의 하위 트리 역시 단일 값일 수 없으므로 false를 반환하게 됩니다.

구현 예제

#include <iostream>
using namespace std;
class Node {
   public:
      int data;
      Node* left, *right;
};
Node* getNode(int data) {
   Node* newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
bool countSingleValuedSubtree(Node* root, int &count) {
   if (root == NULL)
   return true;
   bool left = countSingleValuedSubtree(root->left, count);
   bool right = countSingleValuedSubtree(root->right, count);
   if (left == false || right == false)
      return false;
   if (root->left && root->data != root->left->data)
      return false;
   if (root->right && root->data != root->right->data)
      return false;
      count++;
   return true;
}
int countSingleValSubtree(Node* root) {
   int count = 0;
   countSingleValuedSubtree(root, count);
   return count;
}
int main() {
   Node* root = getNode(5);
   root->left = getNode(1);
   root->right = getNode(5);
   root->left->left = getNode(5);
   root->left->right = getNode(5);
   root->right->right = getNode(5);
   cout << "단일 값 하위 트리의 개수: " << countSingleValSubtree(root);
}

실행 결과

단일 값 하위 트리의 개수: 4

이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로, 전체 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 수입니다. 공간 복잡도 역시 재귀 호출 스택 깊이에 비례하여 O(h), 즉 트리의 높이만큼 필요합니다.