使用python对二叉树的所有路径求解

对于二叉树这类结构问题，可能会遇到的问题中有需要求给定的一颗二叉树，这颗二叉树的根节点到叶子节点的所有路径的问题，这也是深度优先搜索算法的一个较为常见的应用。

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

对于以上的三个二叉树，对每一棵二叉树的根节点到叶子结点的所有路径进行输出，分别是：

①["1-2-4","1-3-5","1-3-6"]

②["1-2-3-5","1-2-3-6","1-2-4"]

③["1-2-4-6","1-2-5","1-3"]

对于以上的二叉树的所有路径返回最终是一个列表啊，这个列表的组成元素是字符串，列表成员每个字符串代表的是从根节点到所有叶子节点中的一个叶节点的路径，这也就需要先定义一个列表为最终共的返回结果，在每一条路径上，如果遇到的节点不是叶子几点，就不断的向定义的字符串中添加遇到的元素，并且在此字符串的基础上继续递归访问这个节点的左右子节点，一直到最后遇到叶子节点的时候，就可以将这个字符串添加到定义的最终结果列表中。以下为python实现求二叉树的路径问题的代码：

def AllPath(root):
    res=[]
    str_=''
    dfs(root,res,str_)
    return res
def dfs(root,res,str_):
    if not root:
        return 
    else:
        str_=str_+str(root.val)
        dfs(root.left,res,str_+'-')
        dfs(root.right,res,str_+'-') 
    if not root.left and not root.right:
        res.append(str_)