[leetcode 437] Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

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

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10  

Return 3.

The paths that sum to 8 are:

1. 5 -> 3

2. 5 -> 2 -> 1

3. -3 -> 11

 

 

 

연결된 노드의 합이 sum인 경우를 모두 찾기

 

풀이:

- 재귀함수로 풀기: 재귀는 재귄데 이중 재귀다. 왜냐면 시작점이 꼭 노드가 아녀도 되기 때문이다. 

- 두 가지 재귀 함수를 구현

1) 트리 내에서 재귀: 시작점을 기준으로 left, right child로 가며 합을 구한다.

2) 시작점에 대한 재귀: 트리의 모든 노드를 돌기 위해 시작점 역시 재귀함수를 건다.

 

/**
 * 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 target;
    
    int solve(TreeNode *cur, int sum){
        if(cur == nullptr){
            return 0;
        }
        sum += cur->val;
        int ans = 0;
        ans += (sum == target) ? 1 : 0;
        ans += solve(cur->left, sum);
        ans += solve(cur->right, sum);
        return ans;
    }
    int pathSum(TreeNode* root, int sum) {
        if(root==nullptr){
            return 0;
        }
        target = sum;
        int ans = 0;
        ans += solve(root, 0);
        ans += pathSum(root->left, sum);
        ans += pathSum(root->right, sum);
        return ans;
    }
};