[LeetCode] 437. Path Sum III

😎풀이

1. BFS를 통해 같은 높이의 노드를 우선적으로 targetSum을 생성하는 노드 탐색
2. DFS를 통해 특정 노드부터 하위 노드로 전파되며 각 노드의 합계를 계산
3. targetSum을 이루는 경우의 수 반환

function pathSum(root: TreeNode | null, targetSum: number): number {
    if(!root) return 0
    let paths = 0
    function dfs(node: TreeNode, remainSum: number) {
        if(node.val === remainSum) {
            paths++
        }
        if(node.left) dfs(node.left, remainSum - node.val)
        if(node.right) dfs(node.right, remainSum - node.val)
    }
    const queue = [root]
    while(queue.length) {
        const curr = queue.shift()
        if(curr.left) queue.push(curr.left)
        if(curr.right) queue.push(curr.right)
        dfs(curr, targetSum)
    }
    return paths
};