leetcode medium : Path Sum II

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

Path Sum II - LeetCode

 

음 그냥 간단한 순회문제다.

에러 없이 한번에 해보려고했는데 몇 번 걸렸다. 진짜 안돌려보고 에러 없게 만드는건 어렵구만..

 

최초 답안

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        
        answerlist = []
        
        if not root:
            return []
        
        def traverse(node, sum, path):
            sum += node.val
            path += [node.val]
            
            if not node.left and not node.right:
                if sum == targetSum:
                    answerlist.append(path)
                return
            if node.left:
                traverse(node.left, sum, path[:])
            if node.right:
                traverse(node.right, sum, path[:])
                
        traverse(root, 0, [])
        
        return answerlist

 

코드를 좀더 짧고 간결하게 만들고 싶은데 잘 안된다. 어떻게 해야하지

 

다른 사람의 코드를 보자

def pathSum(self, root, sum):
        res = []
        self.dfs(root, sum, [], res)
        return res
        
    def dfs(self, root, sum, ls, res):
        if root:
			if not root.left and not root.right and sum == root.val:
				ls.append(root.val)
				res.append(ls)
            self.dfs(root.left, sum-root.val, ls+[root.val], res)
            self.dfs(root.right, sum-root.val, ls+[root.val], res)
            
    def pathSum2(self, root, sum):
        if not root:
            return []
        if not root.left and not root.right and sum == root.val:
            return [[root.val]]
        tmp = self.pathSum(root.left, sum-root.val) + self.pathSum(root.right, sum-root.val)
        return [[root.val]+i for i in tmp]
    
    # 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
        
    # DFS + stack I  
    def pathSum4(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 II   
    def pathSum5(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

걍 끝장을 내놓으셨네..ㅋㅋㅋㅋㅋㅋ

같은 알고리즘이어도 나보다 훨씬 깔끔하게 짠다. 역시 고수들이 많아