C++로 노드 합이 주어진 값 x와 같은 서브트리 개수 구하기

이진 트리(binary tree)와 값 x가 입력으로 주어졌을 때, 노드 가중치의 합이 정확히 x가 되는 서브트리(subtree)가 몇 개 존재하는지 찾는 것이 이 문제의 목표입니다.

문제 예시

입력

x = 14. 값들을 입력한 후 생성되는 트리는 아래와 같습니다.

출력

Count of subtrees that sum up to a given value x are: 1

설명

x 값이 14로 주어졌습니다. 그림에서 확인할 수 있듯이 값이 14인 리프 노드는 하나뿐이므로 개수는 1이 됩니다.

입력

x = 33. 값들을 입력한 후 생성되는 트리는 아래와 같습니다.

출력

Count of subtrees that sum up to a given value x are: 2

설명

x 값이 33으로 주어졌습니다. 아래 그림과 같이 노드 가중치의 합이 33이 되는 서브트리가 두 개 존재하므로 개수는 2가 됩니다.

접근 방법

이 접근법에서는 루트 노드의 왼쪽 서브트리와 오른쪽 서브트리의 가중치 합을 재귀적으로 계산한 뒤, 마지막에 루트 노드 자신의 가중치를 더합니다. 계산된 합이 x와 같다면 개수(count)를 1 증가시킵니다.

• 루트를 가리키는 포인터와 함께 Tree_Node 구조체로 트리를 생성합니다.
• insert_Node(int data) 함수는 트리에 새 노드를 추가합니다.
• subtrees_x(Tree_Node* root, int x) 함수는 트리의 루트 포인터와 x를 인자로 받아, 합이 x가 되는 서브트리의 개수를 반환합니다.
• 재귀 호출 과정에서 개수를 누적하기 위해 정적(static) 변수 count를 0으로 선언합니다.
• Tree_Node 타입의 정적 포인터 temp에 루트를 저장하여 시작 노드를 기억해 둡니다.
• 루트 기준 왼쪽·오른쪽 서브트리의 노드 가중치 합을 저장할 변수 Left_subtree와 Right_subtree를 0으로 초기화합니다.
• 루트가 NULL이면 합으로 0을 반환합니다.
• Left_subtree += subtrees_x(root->Left, x)를 통해 왼쪽 서브트리 노드들의 합을 계산합니다.
• Right_subtree += subtrees_x(root->Right, x)를 통해 오른쪽 서브트리 노드들의 합을 계산합니다.
• sum = Left_subtree + Right_subtree + root->data로 현재 서브트리 전체의 합을 구합니다.
• sum이 x와 같으면 count를 1 증가시킵니다.
• temp != root, 즉 현재 노드가 시작 노드가 아니라면 Left_subtree + root->data + Right_subtree를 상위 호출로 반환합니다.
• 마지막으로 count를 반환하며, 이것이 곧 노드 합이 x와 같은 서브트리의 개수입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
    int data;
    Tree_Node *Left, *Right;
};
Tree_Node* insert_Node(int data){
    Tree_Node* new_node = (Tree_Node*)malloc(sizeof(Tree_Node));
    new_node->data = data;
    new_node->Left = new_node->Right = NULL;
    return new_node;
}
int subtrees_x(Tree_Node* root, int x){
    static int count = 0;
    static Tree_Node* temp = root;
    int Left_subtree = 0, Right_subtree = 0;
    if(root == NULL){
        return 0;
    }
    Left_subtree += subtrees_x(root->Left, x);
    Right_subtree += subtrees_x(root->Right, x);
    int sum = Left_subtree + Right_subtree + root->data;
    if(sum == x){
        count++;
    }
    if(temp != root){
        int set = Left_subtree + root->data + Right_subtree;
        return set;
    }
    return count;
}
int main(){
    Tree_Node* root = insert_Node(10);
    root->Left = insert_Node(20);
    root->Right = insert_Node(12);
    root->Left->Left = insert_Node(14);
    root->Left->Right = insert_Node(1);
    root->Right->Left = insert_Node(21);
    root->Right->Right = insert_Node(11);
    int x = 14;
    cout<<"Count of subtrees that sum up to a given value x are: "<<subtrees_x(root, x);
    return 0;
}

실행 결과

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

Count of subtrees that sum up to a given value x are: 1