[LeetCode] 113. Path Sum II

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

Path Sum II - LeetCode

Path Sum II

 

Path Sum 두번째 시리즈다.

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

 

 

Path Sum 1편

https://kohsmos.tistory.com/63

[LeetCode] 112. Path Sum

 

 

첫번째 시리즈와 비슷한 문제다.

다만 이번 문제의 경우엔 루트부터 마지막노드까지의 합이 targetSum이 되는 개수를 내는것이 아닌

방문한 노드를 모두 출력하는 문제다.

 

첫번째 시리즈와 기본적인 풀이방법은 같다.

다만 vector에 현재 노드의 값을 담아줘야 하므로 첫번째 노드처럼 바로 업데이트 하지는 않고,

인자에 루트부터 더해온 값을 하나 만들어 넘겨주자.

인자에 vector도 하나 들어가는데, 이는 루트부터 현재 노드까지 쭉 입력되어있는 벡터다.

마지막 노드에 자식이 없고, 현재까지 더해온값이 targetSum과 같을때, ret벡터에 현재벡터를 추가해준다.

 

전체 풀이 코드

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