C++로 구현하는 이진 트리의 두 잎 노드 간 최대 경로 합

이 문제에서는 각 노드가 값을 가지는 이진 트리(Binary Tree)가 주어지며, 트리 내 두 잎(leaf) 노드 사이의 경로 중 값의 합이 최대가 되는 경로를 찾는 프로그램을 작성해야 합니다.

여기서 말하는 경로란 한 잎 노드에서 다른 잎 노드까지 이어지는 경로를 의미하며, 이 경로가 반드시 루트(root) 노드를 포함할 필요는 없습니다. 즉, 루트를 지나지 않는 경로라도 합이 더 크다면 그것이 정답이 될 수 있습니다.

이진 트리란?

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 자료구조입니다. 이 두 자식 노드는 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)이라고 부릅니다.

문제 예시

다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.

입력 − // 이진 트리
출력 − 24

설명 − 잎 노드 2에서 잎 노드 9까지의 경로가 최대 합을 제공합니다.
(2 + 5 + 6 - 2 + 4 + 9) = 24

문제 해결 접근 방법

이 문제를 해결하기 위해 트리를 순회(traversal)하면서 현재 노드 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 최대 합을 저장하고, 동시에 지금까지 발견한 잎 노드 간 최대 경로 합을 추적합니다.

즉, 모든 노드에 대해 해당 노드의 서브트리들에서 가능한 최대의 '잎-잎' 경로를 계산한 뒤, 이를 전역(global) 최대 경로 합과 비교하여 더 큰 값을 전역 변수에 저장하는 방식입니다.

예시를 통한 단계별 분석

처음 전역 최대 합은 6입니다 (경로 2→5→-1).

이제 노드 6을 루트로 삼는 경우를 확인해 보겠습니다.

• 왼쪽 서브트리: 잎 노드까지의 경로 합은 7과 4이며, 최댓값은 7입니다 (경로 5→2).
• 오른쪽 서브트리: 경로 (1→-3→7)의 합은 5로, 하나의 가능한 경로입니다.

따라서 잎 노드 사이의 경로 합은 다음과 같이 계산됩니다.

왼쪽 서브트리의 잎-루트(6) 최대 합 + 루트 + 오른쪽 서브트리의 잎-루트(6) 최대 합 = 7 + 6 + 5 = 18

기존 전역 최대 경로 합(6)과 비교하면, 새로운 전역 최대 경로 합은 18이 됩니다. 같은 방식으로 모든 노드를 순회하면 최종적으로 24라는 답을 얻게 됩니다.

C++ 구현 코드

두 잎 노드 간 최대 경로 합을 찾는 프로그램은 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    struct Node* left, *right;
};
struct Node* insertNode(int data){
    struct Node* node = new(struct Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int max(int a, int b)
{ return (a >= b)? a: b; }
int maxPathSumLeaf(struct Node *root, int &maxSum){
    if (root==NULL) return 0;
    if (!root->left && !root->right) return root->data;
    int leftSubTree = maxPathSumLeaf(root->left, maxSum);
    int rightSubTree = maxPathSumLeaf(root->right, maxSum);
    if (root->left && root->right){
        maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
        return max(leftSubTree, rightSubTree) + root->data;
    }
    return (!root->left)? rightSubTree + root->data: leftSubTree + root->data;
}
int main(){
    struct Node *root = insertNode(-2);
    root->left = insertNode(6);
    root->right = insertNode(4);
    root->left->left = insertNode(5);
    root->left->right = insertNode(1);
    root->left->left->left = insertNode(2);
    root->left->left->right = insertNode(-1);
    root->left->right->left = insertNode(-3);
    root->left->right->left->left = insertNode(7);
    root->right->left = insertNode(9);
    root->right->right = insertNode(3);
    int maxSum = INT_MIN;
    maxPathSumLeaf(root, maxSum);
    cout<<"주어진 이진 트리의 두 잎 노드 간 최대 경로 합은 "<<maxSum;
    return 0;
}

실행 결과

주어진 이진 트리의 두 잎 노드 간 최대 경로 합은 24

이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)이며, 재귀 호출 스택 깊이만큼의 공간을 사용합니다. 음수 값이 포함된 트리에서도 정확하게 동작한다는 점이 이 접근법의 큰 장점입니다.