The backtracking approach. Python, recursive


  • 0
    C

    I think this question is a good candidate for backtracking.
    Please let me know if it's helpful.
    The key is to use len to keep track where to cut off the sub array. Similar to index in classical backtracking problems.
    Another issue is with the leaf node. If we use set instead of arrays, we could shorten the code.

    class Solution:
        def binaryTreePaths(self, root):
            res = []
            self.helper(root,res,[],0)
            return res
        def helper(self,root,res,sub,len):
            if root is None:
                return
            sub.append(root.val)
            len += 1
            if root.left is None and root.right is None:
                s = "->"
                res.append(s.join(map(str,sub)))
            else:
                self.helper(root.left,res,sub[:len],len)
                self.helper(root.right,res,sub[:len],len)
    

Log in to reply
 

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