Songzi Vong
공부 저장소
알고리즘, 자료구조, 정리노트 모음

437. Path Sum III

437. Path Sum III

문제

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

문제 사이트

Example 1:

그림 Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 Output: 3 Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3

Constraints:

The number of nodes in the tree is in the range [0, 1000].

  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

문제 해석

  • 이진 트리 경로상에 val의 합으로 targetSum을 몇개를 만들 수 있는지 물어보는 문제이다.

구현(self)

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        int count = 0;
        vector<int> v;
        countSum(root, targetSum, v, count);
        return count;
    }
private:
    void countSum(TreeNode* node, int targetSum, vector<int>& path, int& count) {
        if(!node)   return;

        path.push_back(node->val);
        long long sum = 0;
        for(int i = path.size() - 1; i >= 0; --i)
        {
            sum += path[i];
            if(sum == targetSum)
            {
                count++;
            }
        }
        countSum(node->left, targetSum, path, count);
        countSum(node->right, targetSum, path, count);
        path.pop_back();
    }
};

코드 해석

long long sum = 0;
        for(int i = path.size() - 1; i >= 0; --i)
        {
            sum += path[i];
            if(sum == targetSum)
            {
                count++;
            }
        }
  • val 의 범위가 음수도 포함하기 때문에 sum 은 long long 으로 선언
  • node->val 이 들어 올 때마다 합산을 계산해서 targetSum과 같다면 count 를 증가시켜준다.
countSum(node->left, targetSum, path, count);
countSum(node->right, targetSum, path, count);
path.pop_back();
  • 재귀적인 호출은 이진 트리를 왼쪽 오른쪽 전부 훑어보는 방법이다.
  • 핵심은 path.pop_back(); 백트래킹(backtracking) 이다.
  • 백트래킹은 만약 예시 1번의 이진트리가 있다면 처음에는 10 > 5 > 3 > 3 의 순으로 리프노드까지 내려갈 것이다.
  • 그 후 path.pop_back()을 통해 10 > 5 > 3 으로 돌아가 그 다음 오른쪽 서브트리로 가 10 > 5 > 3 > -2 를 진행하는 방법이다.

구현(정답, 더 간단한)

class Solution {
public:
    long long ans = 0;  // 합이 sum인 경로의 개수 저장

    int pathSum(TreeNode* root, int sum) {
        if (root) {
            dfs(root, sum);  // 현재 노드를 루트로 하는 경로 탐색
            pathSum(root->left, sum);  // 왼쪽 서브트리 탐색
            pathSum(root->right, sum); // 오른쪽 서브트리 탐색
        }
        return ans;
    }

    void dfs(TreeNode* root, int sum) {
        if (!root) return;  // 기저 사례: 노드가 없으면 종료
        if (root->val == sum) ans++;  // 현재 노드 포함 경로에서 합이 sum이면 카운트 증가
        dfs(root->left, sum - root->val);  // 왼쪽 자식으로 이동 (남은 합을 넘김)
        dfs(root->right, sum - root->val); // 오른쪽 자식으로 이동 (남은 합을 넘김)
    }
};

Table of Contents