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

Thoughts:

1. DFS

2. if there is no child, then append itself to the list

3. else add current root.val to every element in the returned list

Code

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

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def dfs(root):
            if not root: return []

            left = dfs(root.left)
            right = dfs(root.right)
            merge = []
            merge.extend(left)
            merge.extend(right)
            ans = []

            if not merge:
                ans.append(str(root.val))    
            else:
                for s in merge:
                    ans.append("{}->{}".format(root.val,s))
            return ans

        return dfs(root)