C++로 이진 트리에서 합이 주어진 값과 일치하는 루트 경로 모두 출력하기

문제 개요

이 문제에서는 하나의 이진 트리(Binary Tree)와 합계 S가 주어집니다. 우리가 찾아야 하는 것은 트리의 루트(root)에서 시작하여 임의의 노드까지 이어지는 경로 중에서, 경로에 있는 노드 값들의 합이 주어진 합 S와 정확히 일치하는 모든 경로입니다.

입력 예시

Sum = 14
Output : path : 4 10
4 3 7

위 예시에서 합이 14가 되는 경로는 두 가지입니다. 첫 번째는 루트 4에서 왼쪽 자식 10으로 이어지는 경로(4 + 10 = 14)이고, 두 번째는 루트 4에서 오른쪽 자식 3, 그다음 7로 이어지는 경로(4 + 3 + 7 = 14)입니다.

접근 방법

이 문제를 해결하려면 먼저 이진 트리의 전위 순회(preorder traversal)를 수행해야 합니다. 전위 순회란 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 노드를 방문하는 방식입니다.

순회 과정에서 다음과 같은 작업을 진행합니다.

1. 현재 노드의 값을 누적 합(sum_so_far)에 더하고, 해당 값을 경로(path) 벡터에 추가합니다.
2. 누적 합이 목표 합과 일치하면, 지금까지 저장된 경로를 출력합니다.
3. 왼쪽과 오른쪽 자식 노드에 대해 재귀적으로 동일한 탐색을 수행합니다.
4. 현재 노드에 대한 탐색이 끝나면 백트래킹(backtracking)을 위해 경로에서 마지막 값을 제거(pop)합니다.

이렇게 백트래킹을 활용하면 하나의 경로 벡터만으로도 트리의 모든 경로를 효율적으로 탐색할 수 있습니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    struct Node *left, *right;
};
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
void printPathsUtilSum(Node* curr_node, int sum, int
sum_so_far, vector<int> &path){
    if (curr_node == NULL)
        return;
    sum_so_far += curr_node->key;
    path.push_back(curr_node->key);
    if (sum_so_far == sum ){
        for (int i=0; i<path.size(); i++)
            cout<<path[i]<<"\t";
        cout<<endl;
    }
    if (curr_node->left != NULL)
        printPathsUtilSum(curr_node->left, sum,
    sum_so_far, path);
    if (curr_node->right != NULL)
        printPathsUtilSum(curr_node->right, sum,
    sum_so_far, path);
    path.pop_back();
}
void pathWithSum(Node *root, int sum){
    vector<int> path;
    printPathsUtilSum(root, sum, 0, path);
}
int main (){
    Node *root = insertNode(4);
    root->left = insertNode(10);
    root->right = insertNode(3);
    root->right->left = insertNode(7);
    root->right->right = insertNode(1);
    root->left->left = insertNode(8);
    root->left->right = insertNode(6);
    int sum = 14;
    cout<<"Paths with the given sum are : "<<endl;
    pathWithSum(root, sum);
    return 0;
}

실행 결과

합이 14가 되는 경로는 다음과 같습니다.

4 10
4 3 7

정리

이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)이며, 재귀 호출 스택과 경로 저장에 사용되는 공간 복잡도는 트리의 높이에 비례하여 O(H)입니다. 전위 순회와 백트래킹을 조합하면 루트에서 시작하는 모든 경로를 간결하게 탐색할 수 있다는 점이 핵심입니다.