113. Path Sum II 정답 및 문제풀이 C++

이 문제는 이진트리가 주어지고 targetSum에 맞는 경로를 찾는 문제입니다. 경로를 구하는 문제의 경우 BFS, DFS 등을 이용하지만 최단거리를 구하는게 아닌 경우 DFS를 보통 활용하기 때문에 트리, 경로 라는 힌트로 DFS를 써야겠구나 정도는 먼저 떠올릴 수 있습니다.

사실 저는 한번에 풀지 못했고 풀이를 보면서도 많이 헷갈렸습니다. DFS 숙달이 아직 안되었다는 얘기인데 여러 풀이를 보면서 가장 괜찮은 방법이라고 할 만한 것을 찾았습니다.

포인트는 크게 다음과 같습니다.

 

1. 경로를 담기위한 path 벡터, 답변을 담기위한 2차원 벡터 v

2. path에 담아주고 targetSum 연산

3. 리프노드 인지 검증합니다.

4. 리프노드가 아닐경우 처리

// https://leetcode.com/problems/path-sum-ii/
// 레퍼런스 https://www.youtube.com/watch?v=7yDOius2XSs
#include <bits/stdc++.h>
using namespace std;

/**
 * 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:

    // 전역변수 설정
    vector<vector<int>> v;
    vector<int> path;
    
    void dfs(TreeNode* root, int sum) {
        if(!root) return; // null인 경우 바로 return
        
        path.push_back(root->val);
        sum = sum - root->val; // 22 -> 17 -> 13 -> 2 (분기점 A 도착)

		// 리프노드에 도착하면 검증
        if(!root->left && !root->right && sum==0) {
            v.push_back(path);
        }

        dfs(root->left, sum); // 분기점에서 왼쪽
        dfs(root->right, sum); // 분기점에서 오른쪽
        path.pop_back();
    }
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return v;
    }
};

조금 더 직관적이라고 생각하는 코드

/**
 * 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:
    //전역변수
    vector<int> path;
    vector<vector<int>> v;

    void dfs(TreeNode* root, int targetSum) {
        if(root == nullptr) return;

        path.push_back(root->val);
        targetSum = targetSum - root->val;

        if(root->left == nullptr && root->right == nullptr && targetSum==0) {
            v.push_back(path);
        }

        if(root->left != nullptr){
            dfs(root->left, targetSum);
            path.pop_back();
        }
        if(root->right != nullptr){
            dfs(root->right, targetSum);
            path.pop_back();
        }
        
    }
    
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);

        return v;
    }
};