Leetcode 24. Pathsum2 (DFS, Backtracking)

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

Path Sum II - LeetCode

---

네,,, 다시 만난 백트래킹 문제로 이진트리에서 root에서 leaf노드까지 갔을 때의 경로합이 targetSum에 해당하는 path를 전부 반환하는 문제입니다.

 

여러 시행착오와 다른 분들 자료를 참고하면서 답변을 짜봤습니다

재귀 DFS 방법 )

# 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]]:
        res,path = [],[]
        if not root:
            return []
        self.dfs(root,targetSum,path,res)
        return res
    
    def dfs(self,root,targetSum,path,res):
        if root:
            if not root.left and not root.right and targetSum == root.val:
                path.append(root.val)
                res.append(path)
                return
            self.dfs(root.left,targetSum-root.val,path+[root.val],res)
            self.dfs(root.right,targetSum-root.val,path+[root.val],res)

별도로 dfs 함수를 만들어서 root에 자식노드가 없는 leaf 노드일 때의 합이 targetSum과 같을 시에 res에 추가해주는 방식입니다. path에 append를 넣은 이유는 만약 root노드만 있는 경우를 포함하기 위함입니다.

 

다른 풀이들을 보면서 재귀, BFS, DFS 활용법을 보겠습니다.

 

---

Leetcode에서 늘 좋은 코드를 공유해주시는 OldCodingFarmer님의 코드입니다.

BFS + QUEUE 방법 )

def pathSum3(self, root, sum): 
        if not root:
            return []
        res = []
        queue = [(root, root.val, [root.val])]
        while queue:
            curr, val, ls = queue.pop(0)
            if not curr.left and not curr.right and val == sum:
                res.append(ls)
            if curr.left:
                queue.append((curr.left, val+curr.left.val, ls+[curr.left.val]))
            if curr.right:
                queue.append((curr.right, val+curr.right.val, ls+[curr.right.val]))
        return res

 

BFS인만큼 left 나 right를 먼저 끝까지 파고드는게 아니라, left 혹은 right가 있는 경우 각각 뻗어 나가도록 했습니다.

val + curr.left.val과 val+curr.right.val을 queue의 기본값으로 선제시한 root.val에 더해서 targetSum의 충족여부를 파악했습니다. 

 

DFS + STACK 방법 1 )

Stack은 위에 BFS 에서 QUEUE를 사용한 방식과 거의 유사합니다.

 

  def pathSum(self, root, sum): 
        if not root:
            return []
        res = []
        stack = [(root, sum-root.val, [root.val])]
        
        while stack:
            curr, val, ls = stack.pop()
            if not curr.left and not curr.right and val == 0:
                res.append(ls)
            if curr.right:
                stack.append((curr.right, val-curr.right.val, ls+[curr.right.val]))
            if curr.left:
                stack.append((curr.left, val-curr.left.val, ls+[curr.left.val]))
        return res

 

DFS + STACK 방법 2 )

def pathSum(self, root, s): 
        if not root:
            return []
        res = []
        stack = [(root, [root.val])]
        while stack:
            curr, ls = stack.pop()
            if not curr.left and not curr.right and sum(ls) == s:
                res.append(ls)
            if curr.right:
                stack.append((curr.right, ls+[curr.right.val]))
            if curr.left:
                stack.append((curr.left, ls+[curr.left.val]))
        return res

 

위의 방식과 STACK을 이용한 DFS라는 점은 동일하지만 TARGETSUM을 접근하는 방식이 마이너스를 통해 0이 되는 지점을 찾는지, 혹은 더해서 TARGETSUM을 도달하는 지점을 찾는지의 차이가 있습니다.

 

---

이 문제에서 신기했던 점은 def dfs함수를 만들 때, 베이스 조건으로 if root을 통해 none인 root를 먼저 제외시켜주는 코드가 if not root: return을 제시해주는 것보다 절반 정도의 시간이 소요되었습니다. if 문의 time complexity는 constant time O(n)의 시간이 소요되는 만큼 test case의 차이 인것으로 보입니다.