C++로 구현하는 이진 트리 두 잎 노드 사이의 최소 합 경로 알고리즘

문제 정의

각 노드가 하나의 숫자 값을 가지는 이진 트리가 주어졌을 때, 한 잎(leaf) 노드에서 다른 잎 노드까지 이동할 수 있는 경로 중 합이 가장 작은 경로를 찾는 것이 과제입니다.

예시

위 트리에서 최소 합을 가지는 부분 경로는 다음과 같이 계산되는 -6입니다.

(-4) + 3 + 2 + (-8) + 1

알고리즘 접근 방식

핵심 아이디어는 재귀 호출 과정에서 두 가지 값을 함께 관리하는 것입니다.

• 현재 노드를 루트로 하는 서브트리에서의 최소 루트-잎 경로 합
• 지금까지 발견된 잎 노드 사이의 최소 경로 합

방문하는 모든 노드 X에 대해 왼쪽 서브트리와 오른쪽 서브트리 각각의 최소 루트-잎 경로 합을 구합니다. 그런 다음 두 값에 X의 데이터를 더한 후, 그 합을 현재까지의 최소 경로 합과 비교하여 더 작은 값으로 갱신합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
typedef struct node {
   int data;
   struct node *left;
   struct node *right;
} node;
node *newNode(int data) {
   node *n = new node;
   n->data = data;
   n->left = NULL;
   n->right = NULL;
   return n;
}
int getMinPath(node *root, int &result) {
   if (root == NULL) {
      return 0;
   }
   if (root->left == NULL && root->right == NULL) {
      return root->data;
   }
   int leftSum = getMinPath(root->left, result);
   int rightSum = getMinPath(root->right, result);
   if (root->left && root->right) {
      result = min(result, root->data + leftSum + rightSum);
      return min(root->data + leftSum, root->data + rightSum);
   }
   if (root->left == NULL) {
      return root->data + rightSum;
   } else {
      return root->data + leftSum;
   }
}
int getMinPath(node *root) {
   int result = INT_MAX;
   getMinPath(root, result);
   return result;
}
node *createTree() {
   node *root = newNode(2);
   root->left = newNode(3);
   root->right = newNode(-8);
   root->left->left = newNode(5);
   root->left->right = newNode(-4);
   root->right->left = newNode(1);
   root->right->right = newNode(10);
   return root;
}
int main() {
   node *root = createTree();
   cout << "Minimum sum path = " << getMinPath(root) << endl;
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum sum path = -6

코드 설명

getMinPath 함수는 재귀적으로 트리를 순회하며 동작합니다. 잎 노드에 도달하면 해당 노드의 값을 반환하고, 자식이 하나뿐인 노드는 존재하는 쪽 서브트리의 합에 자신의 값을 더해 반환합니다. 양쪽 자식이 모두 있는 노드에서는 두 서브트리의 최소 경로 합을 연결하여 잎-잎 경로를 완성하고, 이를 참조 변수 result에 저장된 최솟값과 비교해 갱신합니다. 이 방식은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다.