[dfs] 113번 Path Sum II

문제

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

이진 트리의 루트와 정수 targetSum이 주어지면 경로의 노드 값의 합계가 targetSum과 같은 모든 루트-잎 경로를 반환합니다. 각 경로는 노드 참조가 아닌 노드 값 목록으로 반환되어야 합니다.

루트-리프 경로는 루트에서 시작하여 리프 노드에서 끝나는 경로입니다. 잎은 자식이 없는 노드입니다.

예시

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

제약

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

코드

const pathSum = (root, targetSum) => {
    const res = []
    
    const dfs = (node, sum, path) => {
        if (!node.left && !node.right && sum + node.val === targetSum) {
		        res.push([...path, node.val])
        }
        node.left && dfs(node.left, sum + node.val, [...path, node.val]);
        node.right && dfs(node.right, sum + node.val, [...path, node.val]);
    }
    
    root && dfs(root, 0, []);
    return res;
};

풀이

경로를 구하는 문제로 dfs문제이다.

자식노드로 이동하면서 그동안 어떤 경로를 이동했는지를 알기위한 path 인자와 리프노드까지 이동하면서 각 노드들의 합을 축적할 sum 인자를 명시하였다.

재귀진행 방식은 왼쪽 자식노드와 오른쪽 자식노드가 각각 존재할 때 각각 재귀를 진행하고 sum 에는 현재 노드의 값을 더해서 넘김으로써 sum 을 축적하고 path 에는 현재 노드를 추가함으로써 경로를 축적하여 재귀를 진행한다.

재귀의 종료조건으로 리프노드에 도달했을때 (!node.left && !node.right) 리프노드까지 축적해온 sum 과 현재 노드의 값을 합하여 targetSum 과 값이 동일할 경우 res 에 그동안 축적해온 path 를 푸쉬한다.