题目描述：

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

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

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

题目大意：

给定一棵二叉树，返回所有“根到叶子”的路径。

例如，给定下面的二叉树：

   1
 /   \
2     3
 \
  5

所有“根到叶子”路径为：

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

解题思路：

树的遍历，DFS或者BFS均可。

Python代码（DFS版本）：

# 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.ans = []
        if root is None:
            return self.ans
        def dfs(root, path):
            if root.left is None and root.right is None:
                self.ans += path,
            if root.left:
                dfs(root.left, path + "->" + str(root.left.val))
            if root.right:
                dfs(root.right, path + "->" + str(root.right.val))
        dfs(root, str(root.val))
        return self.ans

下面是一段精炼的Python DFS代码，摘自LeetCode Discuss。

链接地址：https://leetcode.com/discuss/52020/5-lines-recursive-python

# 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):
        if not root:
            return []
        return [str(root.val) + '->' + path
                for kid in (root.left, root.right) if kid
                for path in self.binaryTreePaths(kid)] or [str(root.val)]

Python代码（BFS版本）：

# 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):
        from collections import deque
        if root is None:
            return []
        queue = deque( [ [root, str(root.val)] ] )
        ans = []
        while queue:
            front, path = queue.popleft()
            if front.left is None and front.right is None:
                ans += path,
                continue
            if front.left:
                queue += [front.left, path + "->" + str(front.left.val)],
            if front.right:
                queue += [front.right, path + "->" + str(front.right.val)],
        return ans

 

本文链接：http://bookshadow.com/weblog/2015/08/16/leetcode-binary-tree-paths/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码