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
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.