Python dfs solution with clear comments


  • 0
    class Solution(object):
        def pathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: List[List[int]]
            """
            def dfs(root,res,path,sum):
                # the path is not valid if current root is None
                if not root:
                    return
                # add current root value to path
                path.append(root.val)
                # valid path, append to final solution
                if root.val == sum and root.left is None and root.right is None:
                    res.append(list(path))
                # recursively find possible solutions
                dfs(root.left,res,path,sum-root.val)
                dfs(root.right,res,path,sum-root.val)
                # before return to previous level, reset the path to previous status
                path.pop()
                
            if not root:
                return []
            res = []
            path = [] # path records node series up to now, which is possible to make up a valid solution
            dfs(root,res,path,sum)
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.