Solution


  • 0
    M

    Approach #1 (Pre-order Traversal) [Accepted]

    The points needed to solve this problem include: 1) we need to know if a node is a "leaf" or not. 2) We need to include the prefixes before the "leaves". From the pre-order traversal we could get the result. So basically, this is a tree traversal problem. The implementation in Python.

    class Solution(object):
        def binaryTreePaths(self, root):
            results =[]
            prefixes = ""
            def preOrderTraversal(predix,root):
                if root is not None:
                    prefixes +="->"+str(root.val) if predix else str(root.val)
                    preOrderTraversal(prefixes ,root.left)
                    preOrderTraversal(prefixes ,root.right)
                    if root.left is None and root.right is None:
                        results.append(prefixes )        
            preOrderTraversal(predix,root)
            return results
    

    Complexity Analysis:
    Time complexity : O(n). This is the time complexity of doing pre-order traversal. Since in-order, pre-order and post-order traversals are Depth-first traversals, they complexity is O(n+m), m is the number of edges. In a binary tree, the maximum number of edges is n-1. Thus the time complexity is O(n+n-1), which is O(n).
    Space complexity : O(n*log(n)). The space saved in the results is decided by the number of leaves (n/2), and each one takes the height of the tree(log(n)) as maximum space.


Log in to reply
 

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