题目描述：

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"]`

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
``````

``````# 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
``````

Pingbacks已关闭。