437. Path Sum III

Path Sum III - LeetCode

 

주어진 이진 트리에서 특정 합계(targetSum)를 갖는 경로의 개수를 찾는 문제입니다. 경로는 부모에서 자식으로만 이동할 수 있습니다.

 

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

 

풀이과정 설명:

1. pathSum 메서드는 주어진 이진 트리에서 경로의 개수를 찾습니다.
2. 재귀적으로 트리를 순회하며 각 노드에서 시작하는 경로의 합이 주어진 targetSum과 같은 경우를 찾습니다.
3. countPaths 메서드는 특정 노드에서 시작하는 경로의 개수를 찾습니다.
4. 재귀적으로 좌측 서브트리와 우측 서브트리를 호출하여 경로의 합이 targetSum과 같은 경우를 찾고, 그 개수를 누적합니다.
5. 최종적으로 모든 노드를 방문하여 경로의 개수를 반환합니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        return countPaths(root, targetSum)
            + pathSum(root.left, targetSum)
            + pathSum(root.right, targetSum);
    }

    public int countPaths(TreeNode node, int targetSum){
        if(node == null) return 0;

        int count = 0;
        if(node.val == targetSum) count++;

        count += countPaths(node.left, targetSum - node.val);
        count += countPaths(node.right, targetSum - node.val);

        return count;
    }
}