LeetCode 113(Path Sum II, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• 이진트리의 root와 targetSum이라는 정수가 주어졌을 때, 각 노드의 합이 targetSum과 같으면서 root-to-leaf로 가는 모든 path를 구해서 list에 저장하여 반환
  • 여기서 root-to-leaf path란 root 에서 시작해서, leaf node로 끝나는 path를 의미하며, leaf란 children이 없는 node를 의미한다. 
• 예시1) 이진 트리가 아래와 같이 생겼고, targetSum이 22일 때
  • 5 → 4 → 11 → 2 or 5 → 8 → 4 → 5 로 가면 path의 합이 22가 나오므로, 두 list를 반환한다.
  • 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]]

3. 처음 풀이

• backtracker를 사용하였다. 
  • root, path, targetSum을 인자로 받는 backtrack이라는 함수를 만들고, 
  • root 자체가 없으면 None을 반환
  • root 가 끝까지 도달했으면 (root.left와 root.right가 둘다 None이면)
    • 현재의 targetSum에 root.val을 뺀 값이 0이라면 
      • path에 root.val을 추가한 다음 해당 path를 output에 append하여 반환하고,
      • path를 pop시켜 원래 상태로 바꾸어놓는다. 
  • root가 끝에 도달하지 않았다면,
    • path에 root.val을 append하고,
    • root.left, root.right에 대해 backtrack을 시켜주었다.
      • 이 때, targetSum은 현재의 root.val을 뺀 값으로 업데이트 해두고
      • 마지막으로 path를 pop시켜 원래 상태로 바꾸어놓았다. 

# 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]]:
        
        output = []

        def backtrack(root, path, targetSum):
            # root 자체가 없을 때
            if root is None: 
                return
            
            # 끝까지 도달했을 때
            if root.left is None and root.right is None:
                if targetSum - root.val == 0:
                    path.append(root.val)
                    output.append(path[:])
                    path.pop()
                    return

            # 끝이 아닐 때
            else:
                path.append(root.val)
                backtrack(root.left, path, targetSum-root.val)
                backtrack(root.right, path, targetSum-root.val)
                path.pop()

        backtrack(root, [], targetSum)

        return output

 

4. 다른 풀이

• 거의 비슷한 풀이인데,
  • 처음 풀이에서는 root.left 와 root.right가 None인 경우를 제외하고는, root.left, root.right에 대해 재귀를 호출하였는데,
  • 아래처럼 node.left가 있으면 node.left에 대한 재귀를 호출하고, node.right가 있으면 node.right에 대한 재귀를 호출해야 불필요한 호출을 줄일 수 있겠다. 
  • 그리고 위의 풀이에선 root, path, targetSum을 인자로 받고 있는데,
  • 아래의 풀이에선 root, path만 쌓고, sum(path)가 targetSum인지 판단하는것으로 짜여있는 점이 약간 다르다. 
• 추가로 변수명을 root로 썼는데, 좀 더 명확히는 node라는 표현이 맞는것 같다.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:

        output = []

        def dfs(node, nodes_values):
            if not node:
                return

            nodes_values.append(node.val)

            if not node.left and not node.right and sum(nodes_values) == targetSum:
                output.append(nodes_values.copy())

            if node.left:
                dfs(node.left, nodes_values)
                nodes_values.pop()

            if node.right:
                dfs(node.right, nodes_values)
                nodes_values.pop()

        dfs(root, [])

        return output