[LeetCode 풀이/python] 113. Path Sum II (medium)

문제 설명: 이진트리 root 와 정수 targetSum 이 주어졌을 때, 루트에서 단말 노드까지의 경로에 있는 모든 수의 합이 targetSum 과 같아지는 경로를 모두 리턴하시오. 단말 노드는 자식 노드를 갖지 않는 노드를 가리킴.

 

(Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum. A leaf is a node with no children.)

 

예시 1)

입력: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22  -->  출력: [[5,4,11,2],[5,8,4,5]]

 

예시 2)

입력: root = [1,2,3], targetSum = 5  -->  출력: []

 

예시 3)

입력: root = [1,2], targetSum = 0  -->  출력: []

 

제한 조건:

• 트리의 노드 개수는 [0, 5000] 의 범위 내에 있음
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 직전에 유사한 Path Sum I (LeetCode Q. 112) 문제 풀이를 기반으로 backtracking 을 활용하면 어렵지 않게 풀 수 있다...!
  • 트리에 대해 DFS 를 진행하며 경로를 저장해나가되, 문제의 조건에 맞게 '루트-단말' 경로의 전체 합이 targetSum 값과 같을 경우 해당 경로 path 를 res 에 추가함
    • 한 노드씩 경로를 진행해나갈 때마다 해당 노드의 값을 targetSum 값에서 빼나감으로써 최종적으로 단말 노드 값까지 뺐을 때 0 이 되면 총 경로의 합이 targetSum 과 일치하는 셈!  
    • 어떤 노드의 left, right 가 모두 None (== leaf) & 해당 노드의 값 == 남은 targetSum 값  --> 충족 조건
    • left, right 각각이 존재하는 경우에 대해 left, right 로 진행하여 recursively 탐색

 

• 코드 구현

def pathSum(root: TreeNode, targetSum: int) -> List[List[int]]:
    res = []
    dfs(root, targetSum, [], res)
    return res
    
def dfs(root, targetSum, path, res):
    if not root:
        return False
        
    if (not root.left) and (not root.right) and (root.val == targetSum):
        res.append(path+[root.val])
        return False
    else:
        if root.left:
            self.dfs(root.left, targetSum-root.val, path+[root.val], res)
        if root.right:
            self.dfs(root.right, targetSum-root.val, path+[root.val], res)
        else:  
            ## leaf 도달했으나 경로의 합이 targetSum 과 같지 않음 
            return False

 

• 결과
  • 루트 - 단말까지의 최단 경로만을 고려하므로 단말 노드 개수만큼의 경로가 탐색 대상이 됨
    -->  트리의 깊이를 d = log n 이라 할 때, 단말 노드 수는 최대 2^(d-1) 이므로, O(2^(d-1)) 가 소요됨...!!