[LeetCode] Path Sum II

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

Path Sum II - LeetCode

우선 문제부터 간단하게 요약하면, 

 

binary tree가 주어지면, 해당 트리의 root부터 leaf까지 내려가는 경로중 합이 target number가 되는 경로를 출력해야 하는 문제입니다. 

 

<Solution>

DFS를 사용하여 탐색하도록 문제를 해결하면 됩니다.

 

실제 구현은 아래와 같습니다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int targetSum_;
    vector<vector<int>> answerList;

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == 0) return {};
        targetSum_ = targetSum;
        vector<int> ans;
        dfsLogic(root, 0, ans, 0);
        
        return answerList;
    }

    void dfsLogic(TreeNode* curNode, int curSum, vector<int>& curVector, int saveFlag){
        if(curNode == 0){
            if(curSum == targetSum_ && saveFlag) answerList.push_back(curVector);
            return;
        }

        // on off saveFlag
        saveFlag = (curNode->left || curNode->right) ? 0:1;
        curVector.push_back(curNode->val);
        dfsLogic(curNode->left, curSum+curNode->val, curVector, saveFlag);
        saveFlag = 0;
        dfsLogic(curNode->right, curSum+curNode->val, curVector, saveFlag);
        curVector.pop_back();
    }
};