C++로 이진 트리 각 레벨의 리프 데이터 합계 곱 구하기

개념

주어진 이진 트리(Binary Tree)에 대해 다음과 같은 값을 계산하여 반환하는 문제입니다.

• 트리의 모든 레벨을 순회하면서, 해당 레벨에 리프(leaf) 노드가 존재하면 그 리프 노드들의 데이터 합계를 구합니다. 리프가 없는 레벨은 무시합니다.

• 구한 합계들을 모두 곱한 결과를 반환합니다.

입력 예시 1

다음 트리의 루트
       3
      / \
     8   6
          \\
           10

출력

80

첫 번째 레벨에는 리프가 없습니다. 두 번째 레벨에는 리프 8이 하나 있고, 세 번째 레벨에도 리프 10이 하나 있습니다. 따라서 결과는 8 × 10 = 80입니다.

입력 예시 2

다음 트리의 루트
              3
            /   \
           8     6
          / \     \\
         9   7     10
            / \    / \\
           2  12  5  11

출력

270

처음 두 레벨에는 리프가 없습니다. 세 번째 레벨에는 리프 9가 하나 있고, 마지막 레벨에는 네 개의 리프 2, 12, 5, 11이 있습니다. 따라서 결과는 9 × (2 + 12 + 5 + 11) = 270입니다.

풀이 방법

단순한 접근법(Simple Solution): 트리의 위에서부터 아래까지 재귀적으로 각 레벨의 리프 합계를 계산한 후, 리프가 있는 레벨들의 합계를 서로 곱하는 방식입니다. 이 방법의 시간 복잡도는 O(n²)입니다.

효율적인 접근법(Efficient Solution): 큐(Queue) 기반의 레벨 순회(Level Order Traversal)를 활용합니다. 순회 과정에서 각 레벨을 개별적으로 처리하며, 처리 중인 레벨에 리프 노드가 있는지 확인합니다. 리프가 존재하면 해당 레벨의 리프 노드 합계를 계산하고, 최종적으로 모든 합계의 곱을 반환합니다. 이 방법의 시간 복잡도는 O(n)으로 더 효율적입니다.

예제 코드

/* 이진 트리의 같은 레벨에 있는 모든 리프 데이터의 합을 구하고,
   각 레벨에서 얻은 합계들을 곱하는 반복(iterative) C++ 프로그램 */
#include <bits/stdc++.h>
using namespace std;

// 이진 트리 노드 구조체
struct Node1 {
    int data1;
    struct Node1 *left1, *right1;
};

// 노드가 트리의 리프인지 확인하는 헬퍼 함수
bool isLeaf(Node1* root1){
    return (!root1->left1 && !root1->right1);
}

/* 각 레벨의 모든 리프 노드 합계를 계산하고,
   합계들의 곱을 반환하는 함수 */
int sumAndMultiplyLevelData(Node1* root1){
    // 트리가 비어 있는 경우
    if (!root1)
        return 0;

    int mul1 = 1; /* 결과를 저장할 변수 */

    // 레벨 순회를 위한 빈 큐 생성
    queue<Node1*> q1;

    // 루트를 큐에 삽입
    q1.push(root1);

    // 트리의 레벨 순회 수행
    while (1) {
        // NodeCount1(큐 크기)은 현재 레벨의 노드 수를 나타냄
        int NodeCount1 = q1.size();

        // 현재 레벨에 노드가 없으면 종료
        if (NodeCount1 == 0)
            break;

        // 현재 레벨의 리프 합계 초기화
        int levelSum1 = 0;

        // 현재 레벨에서 리프 노드를 발견했는지 나타내는 불리언 변수
        bool leafFound1 = false;

        // 현재 레벨의 모든 노드를 큐에서 꺼내고(dequeue)
        // 다음 레벨의 모든 노드를 큐에 삽입(enqueue)
        while (NodeCount1 > 0) {
            // 현재 레벨의 다음 노드 처리
            Node1* Node1 = q1.front();

            /* 노드가 리프라면 해당 레벨의 합계 갱신 */
            if (isLeaf(Node1)) {
                leafFound1 = true;
                levelSum1 += Node1->data1;
            }
            q1.pop();

            // 노드의 자식들을 큐에 추가
            if (Node1->left1 != NULL)
                q1.push(Node1->left1);
            if (Node1->right1 != NULL)
                q1.push(Node1->right1);

            NodeCount1--;
        }

        // 최소 한 개의 리프를 발견했다면 결과에 레벨 합계를 곱함
        if (leafFound1)
            mul1 *= levelSum1;
    }

    return mul1; // 결과 반환
}

// 새로운 트리 노드를 생성하는 유틸리티 함수
Node1* newNode(int data1){
    Node1* temp1 = new Node1;
    temp1->data1 = data1;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

// 위 함수들을 테스트하기 위한 드라이버 프로그램
int main(){
    Node1* root1 = newNode(3);
    root1->left1 = newNode(8);
    root1->right1 = newNode(6);
    root1->left1->right1 = newNode(7);
    root1->left1->left1 = newNode(9);
    root1->left1->right1->left1 = newNode(2);
    root1->left1->right1->right1 = newNode(12);
    root1->right1->right1 = newNode(10);
    root1->right1->right1->left1 = newNode(5);
    root1->right1->right1->right1 = newNode(11);

    cout << "최종 곱셈 값 = "
         << sumAndMultiplyLevelData(root1) << endl;
    return 0;
}

실행 결과

최종 곱셈 값 = 270