Today's Challenge

https://leetcode.com/problems/path-sum-ii/

Path Sum II - LeetCode

DFS 를 이용해서 푸는 문제.
뭐든 트리는 Base condition 에 대해 생각하는게 중요한 듯.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(root, path, ans, rem_sum):
            if not root:
                return []

            path.append(root.val)

            if not root.left and not root.right and rem_sum == root.val:
                res.append(list(path))

            dfs(root.left, path, res, rem_sum - root.val)
            dfs(root.right, path, res, rem_sum - root.val)
            path.pop()
        
        dfs(root, [], res, targetSum)
        return res