C++로 이진 트리에서 부모-자식 노드 합계의 최댓값 찾기

이 튜토리얼에서는 C++를 사용하여 이진 트리(Binary Tree)에서 '부모 노드와 두 자식 노드 값의 합'이 가장 큰 경우를 찾는 방법을 알아보겠습니다.

문제의 조건은 다음과 같습니다. 하나의 이진 트리가 주어지며, 왼쪽 자식과 오른쪽 자식을 모두 가진 노드(부모 노드)에 대해서만 해당 노드와 두 자식 노드의 값을 더합니다. 이렇게 계산한 모든 합계 중에서 최댓값을 구해 출력하는 것이 우리의 목표입니다.

알고리즘 접근 방식

이 문제는 재귀(Recursion)를 활용한 트리 순회로 간단히 해결할 수 있습니다.

• 트리를 순회하면서 각 노드를 방문합니다.
• 현재 노드가 왼쪽 자식과 오른쪽 자식을 모두 가지고 있다면, 세 노드의 값을 더한 합계를 계산합니다.
• 계산된 합계를 지금까지 찾은 최댓값과 비교하여 더 큰 값을 저장합니다.
• 모든 노드를 방문할 때까지 왼쪽과 오른쪽 서브트리를 재귀적으로 탐색합니다.

예제 코드

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

// 새로운 노드 생성 및 삽입
struct Node* newNode(int n) {
    struct Node* root = new Node();
    root->data = n;
    root->left = root->right = NULL;
    return root;
}

int maxSum(struct Node* root) {
    if (root == NULL)
        return 0;

    int res = maxSum(root->left);

    // 왼쪽과 오른쪽 자식이 모두 존재하는 경우에만 합계 계산
    if (root->left != NULL && root->right != NULL) {
        int sum = root->data + root->left->data + root->right->data;
        res = max(res, sum);
    }

    return max(res, maxSum(root->right));
}

int main() {
    struct Node* root = newNode(15);
    root->left = newNode(16);
    root->left->left = newNode(8);
    root->left->left->left = newNode(55);
    root->left->right = newNode(67);
    root->left->right->left = newNode(44);
    root->right = newNode(17);
    root->right->left = newNode(7);
    root->right->left->right = newNode(11);
    root->right->right = newNode(41);

    cout << maxSum(root);
    return 0;
}

출력 결과

91

결과 분석

위 예제 트리에서 두 자식을 모두 가진 노드는 다음과 같습니다.

• 루트 노드 15: 15 + 16 + 17 = 48
• 노드 16: 16 + 8 + 67 = 91
• 노드 17: 17 + 7 + 41 = 65

세 경우 중 가장 큰 값은 91이므로, 프로그램은 91을 출력하게 됩니다.

시간 복잡도

이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)입니다. 여기서 N은 트리에 포함된 노드의 개수입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되며, 최악의 경우(편향 트리) O(N), 균형 잡힌 트리의 경우 O(log N)입니다.