LeetCode/Path Sum II

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 코 m / p 로 b ぇ ms / 빠 th - m - 좋은 / ]

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

Return:

마지막 기사 의 발전계에서,
binary tree의 끝에서 끝까지의 root-to-leaf의 합계 값이 변수 sum의 값과 일치하는 path를 모두 반환하는 문제입니다.

해답·해설

해법의 설명에 들어가기 전에, 본 문제와 같이 경로를 순서대로 추적해 목표하는 문제의 해법에는,

Depth-First Search(DFS, 깊이 우선 탐색)

Breadth-First Search(BFS, 폭 우선 탐색)

의 2 종류가 있다고 합니다.
각각의 의미와 구체적인 해법을 나타냅니다.

해법 1

제가 제출한 Iterative 기술입니다. 오랜만에 한 발로 submit이 다니 기뻤습니다.
여기가 DFS에 해당합니다.

트리의 각 루트를 순회하면서 세 요소로 구성된 tuple을 변수 stack에 저장합니다.
첫 번째 요소는 현재 루트, 두 번째 요소는 추적 된 루트 값의 합계, 세 번째 요소는 추적 된 루트 값의 목록입니다.
stack.pop()에서 나중에 저장한 tuple에서 꺼냅니다.
꺼낸 tuple의 두 번째 요소에 루트 값을 더하고 (동시에 세 번째 요소에 루트 값을 append), 값이 sum과 동일한 값이 된 시점의 세 번째 요소를 최종 대답이 될 변수 ans에 저장합니다.

stack의 뒤에 저장되어 있는 tuple만큼 트리의 깊은 계층에 있는 요소가 되기 때문에, stack.pop()로 나중에 저장한 tuple로부터 취해 while loop에 거는 것은, 보다 깊은 계층으로부터 먼저 탐색 하고 있는(=깊이 우선 탐색을 하고 있다)이 됩니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        stack = [(root, root.val, [root.val])]
        while stack:
            curr, val, path = stack.pop()
            if not curr.left and not curr.right:
                if val == sum:
                    ans.append(path)
            if curr.right:
                stack.append((curr.right, val+curr.right.val, path+[curr.right.val]))
            if curr.left:
                stack.append((curr.left, val+curr.left.val, path+[curr.left.val]))
        return ans

해법 2

이어 Iterative BFS.
tree의 각 루트를 순환하면서 세 개의 요소로 구성된 tuple을 변수 queue에 저장합니다.
첫 번째 요소는 현재 루트, 두 번째 요소는 추적 루트 값의 합계, 세 번째 요소는 추적 루트 값 목록입니다. 여기까지는 DFS와 같다.
DFS와 다른 것은, queue.pop(0)로, 이전에 격납한 tuple로부터 꺼내는 곳입니다.

queue의 전방에 격납되고 있는 tuple만큼 트리의 얕은 계층에 있는 요소가 되기 때문에, queue.pop(0)로 전에 격납한 tuple로부터 취해 while loop에 거는 것은, 보다 얕은 계층으로부터 앞으로 에 탐색하고 있는(=폭 우선 탐색을 하고 있다)이 됩니다.

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        queue = [(root, root.val, [root.val])]
        while queue:
            curr, val, path = queue.pop(0)
            if not curr.left and not curr.right:
                if val == sum:
                    ans.append(path)
            if curr.right:
                queue.append((curr.right, val+curr.right.val, path+[curr.right.val]))
            if curr.left:
                queue.append((curr.left, val+curr.left.val, path+[curr.left.val]))
        return ans

해법 3

마지막으로 Recursive 해법은 다음과 같습니다. 생각은 이전의 해법에 가깝기 때문에 해설은 생략합니다.
그러나 좀처럼 Recursive적인 해법을 자력으로 완성시킬 수 없습니다. 뇌가 Iterative적인 생각에 익숙해지고 있네요…

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        if not root:
            return []
        res = []
        self.dfs(root, sum, [], res)
        return res
    def dfs(self, root, sum, ls, res):
        if not root.left and not root.right and sum == root.val:
            ls.append(root.val)
            res.append(ls)
        if root.left:
            self.dfs(root.left, sum-root.val, ls+[root.val], res)
        if root.right:
            self.dfs(root.right, sum-root.val, ls+[root.val], res)