113. Path Sum II [Medium]

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

Path Sum II - LeetCode

 

이진 트리의 루트와 목표 합계 점수를 Input으로 받으면 조건에 맞는 모든 루트-리프 경로를 구하는 문제다.

(리프: 자식 노드가 없는 노드)

 

최종 목표를 저장하는 2차원 벡터 vvec와 내부 임시로 쓰는 1차원 벡터 vec를 써서 해결했(었)다.

source

/**  * 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:     void checkNode(TreeNode* node, int targetSum, vector<vector<int>>& vvec, vector<int>& vec) {         if (nullptr == node) {             return;         }         vec.push_back(node->val);         // 리프노드일 때 목표와 동일한지 체크 후 동일하면 최종 결과 vvec에 추가         if (nullptr == node->left && nullptr == node->right) {             if (targetSum == node->val) {                 vvec.push_back(vec);             }             return;         }         if (nullptr != node->left)         {             checkNode(node->left, targetSum - node->val, vvec, vec);            // 리프 노드에서 push된 데이터 제거             vec.pop_back();         }         if (nullptr != node->right)         {             checkNode(node->right, targetSum - node->val, vvec, vec);            // 리프 노드에서 push된 데이터 제거             vec.pop_back();         }     }     vector<vector<int>> pathSum(TreeNode* root, int targetSum) {         vector<vector<int>> vvec;         vector<int> vec;         checkNode(root, targetSum, vvec, vec);         return vvec;     } };