C++ 알고리즘: 루트에서 리프까지의 경로에서 합이 루트 값과 같은 노드 쌍 찾기

문제 소개

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어집니다. 우리가 확인해야 할 것은 루트에서 리프 노드로 이어지는 경로 안에, 두 노드 값의 합이 루트의 데이터와 같아지는 쌍(pair)이 존재하는지입니다.

다시 말해, 루트 노드부터 리프 노드 사이에 있는 두 노드를 골랐을 때 그 값의 합이 루트 노드의 값과 정확히 일치하는 경우가 있는지를 검사하는 문제입니다.

예제로 이해하기

입력:

출력: Yes

설명:

루트 노드의 값은 7입니다.

합이 7이 되는 노드 쌍으로는 (2, 5)와 (1, 6)이 있습니다.

해결 접근 방법

이 문제는 트리를 순회하면서 해싱(hashing) 기법을 활용하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

1. 정수 값을 저장할 해시 테이블(unordered_set)을 준비합니다.
2. 루트의 왼쪽·오른쪽 자식부터 트리를 깊이 우선(DFS) 방식으로 순회합니다.
3. 현재 노드에 도착하면 루트 값 − 현재 노드 값이 해시 테이블에 이미 있는지 확인합니다. 있다면 현재 경로에서 조건을 만족하는 쌍을 찾은 것이므로 true를 반환합니다.
4. 없다면 현재 노드의 값을 해시 테이블에 삽입한 뒤, 왼쪽과 오른쪽 자식을 재귀적으로 탐색합니다.
5. 현재 노드의 탐색이 끝나면 해시 테이블에서 그 값을 제거합니다. 이를 통해 한 경로의 탐색 결과가 다른 경로에 영향을 주지 않도록 합니다.
6. 모든 경로를 확인한 후에도 쌍을 찾지 못하면 false, 찾았다면 true를 반환합니다.

각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)이며, 해시 테이블에는 현재 경로의 값만 저장되므로 공간 복잡도는 O(H)입니다(N은 노드 수, H는 트리의 높이).

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;

struct Node {

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

struct Node* newnode(int data) {

    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

bool findSumUntil(Node *node, unordered_set<int> &hashTable, int rootVal)
{
    if (node == NULL)
        return false;

    int otherVal = rootVal - node->data;
    if (hashTable.find(otherVal) != hashTable.end())
        return true;

    hashTable.insert(node->data);
    bool isFound = findSumUntil(node->left, hashTable, rootVal) || findSumUntil(node->right, hashTable, rootVal);
    hashTable.erase(node->data);

    return isFound;
}

bool findPairSum(Node *root) {

    unordered_set<int> hashTable;

    return findSumUntil(root->left, hashTable, root->data) || findSumUntil(root->right, hashTable, root->data);
}

int main()
{
    struct Node *root = newnode(7);
    root->left = newnode(2);
    root->right = newnode(3);
    root->left->left = newnode(5);
    root->left->right = newnode(9);
    root->left->left->left = newnode(1);
    root->left->left->right = newnode(6);
    root->right->left = newnode(8);

    if(findPairSum(root))
        cout<<"Pair with sum equal to root value found";
    else
        cout<<"No pairs found";
    return 0;
}

실행 결과

Pair with sum equal to root value found

위 예제 트리에서는 왼쪽 서브트리의 경로 7 → 2 → 5 → 1을 따라 내려가는 도중 (2, 5) 쌍이 발견되므로, 프로그램은 "루트 값과 합이 같은 쌍을 찾았다"는 메시지를 출력합니다.