C++로 이진 트리에서 합이 x가 되는 쌍의 개수 구하기

정수 값들과 변수 x가 주어졌을 때, 이 값들을 이용해 이진 트리를 구성한 뒤 두 노드 값의 합이 x와 같아지는 쌍(pair)의 개수를 찾는 것이 이 글의 목표입니다.

예시

입력 1

int x = 5일 때, 입력값으로 생성되는 이진 트리는 다음과 같습니다.

출력

Count of pairs in a binary tree whose sum is equal to a given value x are: 2

설명

주어진 정수 배열로 이진 트리를 구성한 후, 합이 5가 되는 노드 쌍이 존재하는지 확인합니다. 이때 만들어지는 쌍은 (2, 3)과 (1, 4)로 총 2개입니다.

입력 2

int x = 8일 때, 입력값으로 생성되는 이진 트리는 다음과 같습니다.

출력

Count of pairs in a binary tree whose sum is equal to a given value x are: 3

설명

합이 8이 되는 쌍은 (2, 6), (4, 4), (5, 3)으로 총 3개입니다. 여기서 (4, 4)처럼 값이 같더라도 서로 다른 노드라면 하나의 유효한 쌍으로 계산됩니다.

풀이 접근 방법

• 데이터 필드와 왼쪽·오른쪽 서브트리를 가리키는 포인터를 포함하는 노드 구조체를 정의합니다.
• 정수 값들을 입력받아 왼쪽·오른쪽 포인터에 노드를 연결하는 방식으로 이진 트리를 생성합니다.
• 쌍의 합과 비교할 기준 값 x를 입력받습니다.
• 두 노드 값의 합이 x와 같은지 검사하는 불리언 함수 check를 작성합니다.
• check 함수 안에서 루트가 NULL이면 false를 반환합니다.
• 루트가 ptr과 다르면서 (루트의 데이터 + ptr의 데이터)가 x와 같으면 true를 반환합니다.
• 루트의 왼쪽 포인터와 오른쪽 포인터에 대해 check를 재귀 호출하고, 하나라도 true를 반환하면 true를, 그렇지 않으면 false를 반환합니다.
• 쌍의 개수를 세는 total_pairs 함수를 작성합니다. ptr이 NULL이면 그대로 종료합니다.
• root, ptr, x를 인자로 check를 호출하여 true가 반환되면 total을 1 증가시킵니다.
• ptr의 왼쪽 자식과 오른쪽 자식에 대해 total_pairs를 재귀 호출하여 트리의 모든 노드를 탐색합니다.
• 모든 노드에 대한 검사가 끝나면 각 쌍이 (a, b)와 (b, a) 형태로 두 번씩 세어지므로 total을 2로 나눈 뒤 결과를 출력합니다.

이 알고리즘은 각 노드마다 전체 트리를 한 번씩 순회하므로 시간 복잡도는 O(n²)이며, 공간 복잡도는 재귀 호출 스택의 깊이에 따라 O(h)(h는 트리의 높이)입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct tree_node {
    int data;
    tree_node *left, *right;
};
tree_node* create_node(int data){
    tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
bool check(tree_node* root, tree_node* ptr, int x){
    if(root==NULL){
        return false;
    }
    if (root != ptr && ((root->data + ptr->data) == x)){
        return true;
    }
    if (check(root->left, ptr, x) || check(root->right, ptr, x)){
        return true;
    }
    return false;
}
void total_pairs(tree_node* root, tree_node* ptr, int x, int& total){
    if(ptr == NULL){
        return;
    }
    if(check(root, ptr, x) == true){
        total++;
    }
    total_pairs(root, ptr->left, x, total);
    total_pairs(root, ptr->right, x, total);
}
int main(){
    int x = 5;
    int total = 0;
    tree_node* root = create_node(5);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(1);
    root->left->right = create_node(4);
    root->right->left = create_node(6);
    total_pairs(root, root, x, total);
    total = total / 2;
    cout<<"Count of pairs in a binary tree whose sum is equal to a given value x are: "<< total;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of pairs in a binary tree whose sum is equal to a given value x are: 2