[Binary Tree General][Easy] 112. Path Sum

https://leetcode.com/problems/path-sum/description

 

 

Q. root 에서 leaf까지 가는 경로동안 그 합이 targetSum이 되는 것이 있으면 true를 반환하라. 

 

Solution. 

 - 단순 경로 탐색 문제. 

 - 경로를 가는 동안 노드 값을 누적하고, leaf node인 순간 targetSum을 확인한다. 

 

코드 

bool hasPathSumToLeaf(TreeNode* node, int targetSum, int sum)
{
    if(node == NULL)
        return false;

    sum += node->val;

    if(node->left==NULL && node->right==NULL)
    {
        if(sum == targetSum)
            return true;
        return false;
    }

    bool left = hasPathSumToLeaf(node->left, targetSum, sum);
    bool right = hasPathSumToLeaf(node->right, targetSum, sum);

    if(left || right)
        return true;
    return false;
}

bool hasPathSum(TreeNode* root, int targetSum) {

    if(root == NULL)    return false;

    int sum = 0;

    return hasPathSumToLeaf(root, targetSum, sum);
}

 

결과.