题目
难度：★★☆☆☆
类型：二叉树
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
解答
这道题目与【题目107. 二叉树的层次遍历】十分类似，这里我们也用递归实现。
定义一个函数get_paths，有三个输入：
（1）当前节点；
（2）当前路径列表，从根节点遍历到当前结点所经过的所有结点的值组成的列表；
（3）结果列表，其中每个元素都是一个路径的字符串。
函数的输出是一个布尔量，表示当前结点存在左右子树，如果均有返回True，否则返回None（False）。函数get_paths执行的操作有：
（1）判断输入结点是否为空，如果为空则直接返回None（或False）
（2）将当前结点的值加入到路径列表中；
（3）递归调用本函数获得左右子树的路径结果；
（4）如果到达叶子结点，则将当前结果添加到结果列表中；
（5）返回上一层递归时，弹出路径中的当前结点元素。
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
def get_paths(root, path, res):
if root:
path.append(str(root.val))
left = get_paths(root.left, path, res)
right = get_paths(root.right, path, res)
if not left and not right: # 如果root是叶子结点
res.append("->".join(path)) # 把当前路径加入到结果列表中
path.pop() # 返回上一层递归时，要让当前路径恢复原样
return True
res = []
get_paths(root, [], res)
return res
如有疑问或建议，欢迎评论区留言~
