题目描述
给一棵二叉树，找出从根节点到叶子节点的所有路径。
测试样例
输入：{1,2,3,#,5}
输出：["1->2->5","1->3"]
解释：
1
/ \
2 3
\
5
输入：{1,2}
输出：["1->2"]
解释：
1
/
2
解题思路与方法
由于需要记录从根节点到所有叶子节点的路径，因此需要设置一个全局的变量用于存储这些路径，为方便起见，下文将其简称为“路径集” —— P。
另外，从每个节点到其左右子树都会分别形成一条子路径，简称为sub_path。
1、DFS
DFS在这里应该是最“直线”思维的解题方法，因为题目要求找到所有到叶子节点的路径，而DFS就是一直递归遍历直至遇到叶子节点。
遍历过程中，每走到一个节点先将其加入到当前的子路径sub_path中，如果该节点是叶子节点，则将这个子路径添加到路径集P里。
否则，若节点有左儿子，将递归遍历左子树，同时将子路径sub_path复制一份传递下去；
若节点有右儿子，则递归遍历右子树，同时也将子路径sub_path复制传递下去。
待所有叶子节点都遍历完后，返回路径集P即为所求。
2、BFS
由于题目要求的路径与顺序无关，因此还可用BFS来遍历这棵树，注意遍历过程中，要将节点与对应的路径都加入到队列中。
3、Devide & Conquer
分而治之是一种由大到小，待最小单位解决问题后，再一步步回到上面的层级来的方式。对于每个节点，待其左子树与右子树都处理完成后，对这些子树所得的所有到叶子节点的路径，都在开头加上这个节点本身，最后，返回这个节点下所有到叶子节点的路径（若该节点是叶子节点，那么这里得到的路径即为其自身）。
代码
1、DFS
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
if not root:
return []
# 根到所有叶子的路径
all_path_to_leaf = []
# 根到一个叶子的路径
sub_path_to_leaf = []
self._dfs(root, sub_path_to_leaf, all_path_to_leaf)
return all_path_to_leaf
def _dfs(self, node, path, route):
# 注意将节点的值转换为字符型
path.append(str(node.val))
if not (node.left or node.right):
# 遇到了叶子节点，将该路径加入到总路径集中
route.append('->'.join(path))
return
'''注意一下path要copy下，而route保持为同一个对象'''
if node.left:
# 遍历左子树
self._dfs(node.left, path[:], route)
if node.right:
# 遍历右子树
self._dfs(node.right, path[:], route)
2、BFS
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
if not root:
return []
path_to_leaf = []
deque = [(root, '')]
# BFS
while deque:
node, path = deque.pop(0)
if path:
path += '->{}'.format(str(node.val))
else:
path += str(node.val)
# 遇到叶子节点，将当前路径加入到路径集中
if not (node.left or node.right):
path_to_leaf.append(path)
if node.left:
deque.append((node.left, path))
if node.right:
deque.append((node.right, path))
return path_to_leaf
3、Devide & Conquer
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of the binary tree
@return: all root-to-leaf paths
"""
def binaryTreePaths(self, root):
if not root:
return []
# 以当前节点为根，到其下左、右子树所有叶子节点的路径
path_to_leaf = []
# 左子树中所有到叶子节点的路径
sub_path_left = self.binaryTreePaths(root.left)
# 右子树中所有到叶子节点的路径
sub_path_right = self.binaryTreePaths(root.right)
'''在左、右子树获得的路径的起始位置加入当前节点，
并且加入到路径集中'''
self._add_full_path(root, sub_path_left, path_to_leaf)
self._add_full_path(root, sub_path_right, path_to_leaf)
# 叶子节点的路径集即为其自己
if not (root.left or root.right):
path_to_leaf.append(str(root.val))
return path_to_leaf
def _add_full_path(self, top, sub_paths, repo):
"""
@param top: a root node of tree;
@param sub_paths: a path set containing all the paths to leaves;
@param repo: a path repository
"""
for path in sub_paths:
full_path = '{}->{}'.format(str(top.val), path)
repo.append(full_path)
