Python Solution with Detailed Explanation


  • 0
    G

    Solution

    Binary Tree Paths https://leetcode.com/problems/binary-tree-paths/

    Standard Pre-Order Traversal

    • Keep a list so_far to track the path so_far
    • Use the standard backtracking template to enumerate all paths
    • Time Complexity: We traverse every node just once. For every leaf, we copy the path so_far into result list. Say there are L leaves and average lenght of each path is K. Then the complexity is O(LK). For a balanced tree, L ~ N (N//2) and K is ~Lg(N), so we have O(N * lg(N)). For a general worst case, we have O(N^2).
    • Space Complexity: O(N).
    class Solution:
        # @param {TreeNode} root
        # @return {string[]}
        def binaryTreePaths(self, root):
            result = []
            if root:
                self.helper(root, [], result)
            return result
        
        def helper(self, root, so_far, result):
            if root.left is None and root.right is None:
                so_far.append(root.val)
                result.append("->".join(map(str, so_far)))
                so_far.pop()
            else:
                so_far.append(root.val)
                if root.right:
                    self.helper(root.right, so_far, result)
                if root.left:
                    self.helper(root.left, so_far, result)
                so_far.pop()
            return
    

Log in to reply
 

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