"""Leetcode 257. Binary Tree Paths
Easy

URL: https://leetcode.com/problems/binary-tree-paths/

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:
Input:
   1
 /   \
2     3
 \
  5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
"""

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        pass


def main():
    pass


if __name__ == '__main__':
    main()

@@ -495,16 +495,19 @@
 Solution
+DFS
 (object)
@@ -520,151 +520,1170 @@
 def 
-binaryTreePaths(self, root):%0A        %22%22%22%0A        :type root: TreeNode%0A        :rtype: List%5Bstr%5D%0A        %22%22%22%0A        pass%0A%0A%0Adef main():%0A    pass
+_dfs(self, root, cur_path, paths):%0A        # Concat root's value.%0A        cur_path += str(root.val)%0A%0A        # Check if root is leaf or not.%0A        if not root.left and not root.right:%0A            paths.append(cur_path)%0A%0A        # Start DFS for left and right nodes respectively.%0A        if root.left:%0A            self._dfs(root.left, cur_path + '-%3E', paths)%0A        if root.right:%0A            self._dfs(root.right, cur_path + '-%3E', paths)%0A%0A    def binaryTreePaths(self, root):%0A        %22%22%22%0A        :type root: TreeNode%0A        :rtype: List%5Bstr%5D%0A%0A        Time complexity: O(n).%0A        Space complexity: O(logn) for balanced tree; O(n) for singly-linked list.%0A        %22%22%22%0A        # Check base case.%0A        if not root:%0A            return %5B%5D%0A%0A        # Apply DFS to collect paths.%0A        paths = %5B%5D%0A        cur_path = ''%0A        self._dfs(root, cur_path, paths)%0A        return paths%0A%0A%0Adef main():%0A    # Input:%0A    #    1%0A    #  /   %5C%0A    # 2     3%0A    #  %5C%0A    #   5%0A    # Output: %5B%221-%3E2-%3E5%22, %221-%3E3%22%5D%0A    root = TreeNode(1)%0A    root.left = TreeNode(2)%0A    root.right = TreeNode(3)%0A    root.left.right = TreeNode(5)%0A%0A    print SolutionDFS().binaryTreePaths(root)
 %0A%0A%0Ai

Complete dfs sol