Simple DFS Solution with recursive method


  • 0
    J

    Since it wants every path from root to leaf, it's naturally to think of Deep First Search.
    With Deep First Search, we can iterate every path from root to leaves, but the problem here is how to keep track of each path.

    With the expected result in mind, we need to pop out the current node only if all children of this node traversed. Backtracking does this exactly.

    To do DFS with backtracking, we can use a recursive way to do this:

    Here is the full solution:

    class Solution(object):
        def get_path(self, root, result, temp):
            root_value = str(root.val)
            if not root.left and not root.right:
                temp.append(root_value)
                result.append('->'.join(temp))
                temp.pop()
            else:
                temp.append(root_value)
                if root.left:
                    self.get_path(root.left, result, temp)
                if root.right:
                    self.get_path(root.right, result, temp)
                temp.pop()
                
                
        def binaryTreePaths(self, root):
            """
            :type root: TreeNode
            :rtype: List[str]
            """
            result = []
            temp = []
            if root:
                self.get_path(root, result, temp)
            return result
    

Log in to reply
 

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