Python DFS, iteratively


  • 0
    Y

    I use DFS and stack with 3 items (node, path, sum)

    class Solution(object):
        def pathSum(self, root, sum):
            if not root: return []
            stack=[(root,[root.val],root.val)]
            res=[]
            while stack:
                root,path,s=stack.pop()
                if not root.right and not root.left:
                    if s==sum:
                        res.append(path)
                if root.left:
                    stack.append((root.left,path+[root.left.val],s+root.left.val))
                if root.right:
                    stack.append((root.right,path+[root.right.val],s+root.right.val))
            return res
    #114 / 114 test cases passed.
    #Status: Accepted
    #Runtime: 66 ms
    

Log in to reply
 

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