[LeetCode] 437. Path Sum III

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

Path Sum III - LeetCode

Path Sum II

 

Path Sum 세번째 시리즈다.

이전 시리즈를 먼저 풀고 풀어보길 권한다.

 

 

Path Sum 1편

https://kohsmos.tistory.com/63

[LeetCode] 112. Path Sum

Path Sum 2편

https://kohsmos.tistory.com/64

[LeetCode] 113. Path Sum II

 

 

 

오늘의 문제이다.

시리즈 문제이길래 1번부터 풀어봤다.

이번 문제는 루트부터 마지막 노드가 아닌, 어떤 노드들의 경로의 합이 targetSum이 되는 개수를 출력하는 문제다.

노드들의 경로는 물론 아래방향으로만 진행되어야 한다.

 

1,2번 문제와는 조금. 아주 조금 다른문제다.

하지만 이 문제는 어떻게 보면 부분합을 구하는 문제와 똑같다.

부분합의 경우에는 숫자가 배열로 되어 있을때, index가 연속해있는 어떤 부분의 합이 목표값이 되는지 찾는 문제인데,

배열이 이진 트리로 바뀌었다고 보면 된다.

 

부분합 문제를 구할때 가장 먼저 해야하는 일은 각 배열의 수를 현재까지의 합으로 업데이트 해주는 일이다.

이 경우도 마찬가지다. 트리들을 훑으며 현재 경로의 모든 노드들의 합으로 현재 노드의 값을 바꿔주자.

그러고 부분합을 비교해야하는데, 부분합을 구하는 방법은 아래와 같다.

배열을 예시로 들었을때, Arr1 = [a1, a2, a3, ... , an] 이 있다고 하자.

이를 우리는 Arr1 = [a1=s1, a1+a2=s2, a1+a2+a3=s3, ... , a1+a2+a3+...+an = sn] 으로 업데이트 해줬다.

이때, 만약 a5+a6+a7+...+a12 를 구하고 싶다면 어떻게 해야할까?

기존 배열에서 for 문으로 a5 부터 a12까지 더해줘도 되지만,

합을 저장한 배열에서는 s12 - s4를 해주면 바로 원하는 값을 구할 수 있다.

 

s12 = a1 + a2 + a3 + a4 + a5 + a6 + ... + a12

s4   = a1 + a2 + a3 + a4

이므로,

s12 - s4 = a5 + a6 + ... + a12

 

이번 문제에서는 이를 이용할 것이다.

 

트리를 각 노드까지의 합으로 바꿔주는 작업은 해주었다.

이때 해당 경로에 있던 모든 변경된 노드값을 벡터 vec에 담아주고

현재 변경된 노드값에서 벡터에 있는 모든값을 빼서 그게 targetSum이 되는지 비교해주면 각각의 부분합을 구해줄 수 있게 된다.

 

전체 풀이 코드

class Solution {
public:
    int ret=0;
    int targetSum;
    int pathSum(TreeNode* root, int targetSum) {
        this->targetSum = targetSum;
        vector<int> vals;
        run(root, 0, vals);
        return this->ret;
    }
    void run(TreeNode* node, int pre_val, vector<int> vals) {
        if (!node) return;
        if (node->val+pre_val==this->targetSum) this->ret++;
        for (int val:vals) if (node->val+pre_val - val==this->targetSum) this->ret++;
        vals.push_back(pre_val+node->val);
        run(node->left, pre_val+node->val, vals);
        run(node->right, pre_val+node->val, vals);
    }
};