[Leetcode] 437. Path Sum III

1. 문제링크

Path Sum III - LeetCode

 

 

2. Key Point - targetSum은 어디에나 존재할 수 있다, 모든 노드를 탐색하자

이 꼭 시작과 끝이 root에서 leaf까지의 sum이 아니어도 된다.

 

 

targetSum = -1인 경우, 답 : 4개

현재까지의 sum이 targetSum이더라도 아래 노드를 계속 탐색한다 (핑크색)

 

 

3. Solution

class Solution {
public:
    int ans = 0;
    void solve(TreeNode* node, long long sum){
        if(!node) return;

        if(node->val == sum){
            ans++;
        }
        solve(node->left, sum - node->val);
        solve(node->right, sum - node->val);
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        solve(root, targetSum);
        pathSum(root->left, targetSum);
        pathSum(root->right, targetSum);

        return ans;        
    }
};