[LeetCode] 437. Path Sum III, Medium

1. 문제

• 이진 트리가 주어질 때, 경로 상의 합이 targetSum과 같아지는 경우의 수를 구하라.
• 단, 경로는 root부터 시작해서 leaf에서 끝날 필요가 없고, 중간부터 탐색할 수도 있다. 

2. 해결

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function DFS(node: TreeNode | null, targetSum: number): number {
    if (!node) return 0;

    let count = 0;

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

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

    return count;
}

function pathSum(root: TreeNode | null, targetSum: number): number {
    if(!root) return 0;

    const current = DFS(root, targetSum);

    const left = pathSum(root.left, targetSum);
    const right = pathSum(root.right, targetSum);
    
    return current + left + right;
};

• 못 풀었다. 루트 노드부터 시작하는 경로의 합은 구할 수 있었지만, 각 노드부터 시작하는 경우를 찾지 못했다.
• 경로 합을 찾는 함수를 DFS로 가정하고, 각 모든 노드를 루트로 시작할 수 있게끔 재귀 호출해주면 된다.
• 즉, 처음은 root 노드부터 경로의 합을 찾고 다음은 root의 왼쪽 서브트리가 루트 노드가 되게끔 호출하고 root의 오른쪽 서브트리가 루트 노드가 되게 호출하면 모든 경우를 찾을 수 있다.