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

For example, given the following binary tree: 

1
2
3
4
5
   1
 /   \
2     3
 \
  5

All root-to-leaf paths are: 

1
["1->2->5", "1->3"]

思路

利用深度优先遍历，可以得到树从根节点到叶子节点的所有路径。递归直到访问到叶子节点，此时向结果数组加入一个路径的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        self.res = []
        if (root):
            self.DFS(root, '')
            return self.res
        else:
            return self.res
    def DFS(self, root, string):
        if (root):
            val = root.val
            string += str(val)
            if (root.left is None and root.right is None):
                self.res.append(string)
            else:
                string += '->' 
                self.DFS(root.left, string)
                self.DFS(root.right, string)