leetcode : Path Sum II

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

Path Sum II - LeetCode

트리를 쭉 순회하다가 리프노드에서 조건이 맞는지 검사하고 정답 리스트에 path를 추가해주면 된다. 매우 간단함.

참고로 recursive call 할 때 path를 복사하는 방법은 가독성은 좋으나 성능에 악영향이 심해서 스택처럼 push&pop하는게 submission 후 결과가 잘나온다.

 

# 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]]:
        answer = []
        def dfs(node, remaining):
            remaining -= node.val
            
            if not node.left and not node.right:
                if remaining == 0:
                    answer.append(path[:])
                return
            
            if node.left:
                path.append(node.left.val)
                dfs(node.left, remaining)
                path.pop()
            if node.right:
                path.append(node.right.val)
                dfs(node.right, remaining)
                path.pop()
        
        if root:
            path = [root.val]
            dfs(root, targetSum)
            
        return answer
                

시간복잡도는 최대 O(N^2)이다. 

이렇게 skewed된 트리에서 모든 노드 값이 0이고 targetsum도 0이면 리프노드에 도달할때마다 2,3,4,5,..길이의 path를 정답리스트에 복사해 넣어야된다. 정답리스트를 제외하면 공간복잡도는 O(N)이 된다.