Python Easy DFS (Recursive + Iterative) Solution


  • 2
    G

    Recursive:

    def binaryTreePaths(self, root):
        if not root:
            return []
        res = []
        self.dfs(root, "", res)
        return res
    
    def dfs(self, node, path, res):
        if not node:
            return
        if not node.left and not node.right:
            res.append("{}{}".format(path, node.val))
        self.dfs(node.left, "{}{}->".format(path, node.val), res)
        self.dfs(node.right, "{}{}->".format(path, node.val), res)
    

    Iterative:

    def binaryTreePaths(self, root):
        if not root:
            return []
        res = []
        stack = [(root, "")]
        while stack:
            node, path = stack.pop()
            if not node:
                continue
            if not node.left and not node.right:
                res.append("{}{}".format(path,node.val))
            stack.append((node.left, "{}{}->".format(path,node.val)))
            stack.append((node.right, "{}{}->".format(path,node.val)))
        return res

Log in to reply
 

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