경로 합계 II

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

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

예 1:



입력: 루트 = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
출력: [[5,4,11,2],[5,8,4,5]]
설명: 합계가 targetSum과 같은 경로가 두 개 있습니다.
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

예 2:



입력: 루트 = [1,2,3], targetSum = 5
출력: []

예 3:

입력: 루트 = [1,2], targetSum = 0
출력: []

제약:

트리의 노드 수가 [0, 5000] 범위에 있습니다.

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

해결책:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        paths = [(root, [root.val] if root else 0)]
        i = 0
        op = []
        while i < len(paths):
            curr, val = paths[i]
            if curr:
                if not curr.left and not curr.right:
                    if sum(val) == targetSum:
                        op.append(val)
                if curr.left:
                    paths.append((curr.left, val + [curr.left.val]))
                if curr.right:
                    paths.append((curr.right, val + [curr.right.val]))
            i += 1
        return op