[c++] 루트-리프 경로 합(Root-to-Leaf Path Sum)

12 Dec 2023

예를 들어, 다음과 같은 바이너리 트리가 있다고 가정해봅시다.

이때, 1 → 2 → 4의 경로의 합은 7이 되고, 1 → 2 → 5의 경로의 합은 8이 됩니다.

이 문제를 해결하기 위해, 우리는 DFS(깊이 우선 탐색) 알고리즘을 사용할 수 있습니다. 재귀적 방법을 통해 트리의 모든 경로를 탐색하고 경로의 합을 계산할 수 있습니다.

아래는 C++로 구현된 루트-리프 경로 합을 계산하는 간단한 예시 코드입니다.

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool rootToLeafPathSum(TreeNode* root, int sum) {
    if (root == NULL) {
        return false;
    }
    if (root->left == NULL && root->right == NULL && root->val == sum) {
        return true;
    }
    return rootToLeafPathSum(root->left, sum - root->val) || rootToLeafPathSum(root->right, sum - root->val);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int targetSum = 8;
    if (rootToLeafPathSum(root, targetSum)) {
        cout << "Path with sum " << targetSum << " exists.";
    } else {
        cout << "Path with sum " << targetSum << " does not exist.";
    }
    return 0;
}

이 예시는 1을 루트로 하는 트리에서 루트-리프 경로 합이 목표값인지를 판별하는 기능을 구현한 코드입니다.

이러한 문제를 해결할 때는 탐색 알고리즘을 사용하여 모든 가능한 경로를 탐색하고, 목표값과 비교하여 조건에 맞는 경로가 존재하는지 확인하면 됩니다.