Root-to-Leaf Paths

Write leaf_paths(root) that returns every path from the root of a binary tree down to a leaf, a node with no children. Write each path as a string of its values joined by '->', such as '5->3->1', and list the paths in the order of their leaves from left to right (the order in which a search that always tries the left child before the right one reaches them). An empty tree has no paths, so it gives [].

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

      5
     / \
    3   8
   / \   \
  1   4   9

leaf_paths(build([5, 3, 8, 1, 4, None, 9]))  # returns ['5->3->1', '5->3->4', '5->8->9']
leaf_paths(build([7]))  # returns ['7']
leaf_paths(build([2, -4, None, 6]))  # returns ['2->-4->6']

The drawing shows the first tree. A negative value keeps its minus sign, as in the last example.

Constraints

• 0 to 2,000 nodes, at most 300 levels deep.
• Values are integers from -1,000 to 1,000, and different nodes can hold the same value.