- 问题描述
- 递归遍历 Tree 的大原则
- 第一种，直接递归， 32 ms
- DFS method 24 ms
- 一边递归，一边构造，在叶子节点确认加入结果的list，这个方法更多的是一种从前往后的思想 24 ms
问题描述
Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Explanation: All root-to-leaf paths are: 1->2->5, 1->3
Example:
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
递归遍历 Tree 的大原则
一般都是直接思考叶子节点，左右子树同时开工，然后再往上。
第一种，直接递归， 32 ms
一边递归，一边构造。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if root == None:
return []
# leaf node 叶子节点
if root.left == None and root.right == None:
return [str(root.val)]
# execute the following code from the leaf nodes up
string_path = [str(root.val)+'->'+path for path in self.binaryTreePaths(root.left)]
string_path += [str(root.val)+'->'+path for path in self.binaryTreePaths(root.right)]
return string_path
很明显，对于示例来说，root 节点为 2 时的左子节点为 None，返回空 list， 而右子节点 5 则返回 ['5']，
因此这两行
string_path = [str(root.val)+'->'+path for path in self.binaryTreePaths(root.left)]
string_path += [str(root.val)+'->'+path for path in self.binaryTreePaths(root.right)]
得到的 string_path 为 ['2->5']
对于 root 为 1 的节点，此时, string_path = [str(root.val)+'->'+path for path in self.binaryTreePaths(root.left)] 使得 ['2->5'] 变成了 ['1->2->5']
右 子节点返回了 ['3'],此时 string_path += [str(root.val)+'->'+path for path in self.binaryTreePaths(root.right)] 中右边的东西为 ['1->3']
因此上面两行代码过后 return 的结果是 ["1->2->5", "1->3"]
DFS method 24 ms
这个也是纯粹利用递归的思想找到叶子节点，然后再去找字符串。
即，先递归，再构造。
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
leaf_nodes=[]
parent_nodes={}
# 构建叶子节点的list，以及各个节点的父节点的字典
def dfs(root):
if root == None:
return None
if root.left == None and root.right == None:
leaf_nodes.append(root)
if dfs(root.left):
parent_nodes[root.left]=root
if dfs(root.right):
parent_nodes[root.right]=root
return 1
dfs(root)
tmp_results=[]
for leaf_node in leaf_nodes:
tmp_list=[str(leaf_node.val)]
tmp_node = leaf_node
while tmp_node != root:
tmp_node = parent_nodes[tmp_node]
tmp_list.append(str(tmp_node.val))
tmp_results.append(tmp_list)
pass
results=[]
for tmp in tmp_results:
tmp.reverse()
results.append("->".join(tmp))
return results
思路就是，先通过 dfs 找出所有叶子节点，同时构建一个字典用于保存叶子节点的父节点，以及父节点的父节点信息。
再根据这个字典以及叶子节点，重建所有的path。
一边递归，一边构造，在叶子节点确认加入结果的list，这个方法更多的是一种从前往后的思想 24 ms
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
all_paths=[]
def findPath(root,tmp_result):
# 先初始化根节点
if len(tmp_result)==0:
tmp_result=str(root.val)
else: # 一路添加子节点
tmp_result+='->'+str(root.val)
pass
# 终于到叶子节点了，从这里开始返回
if root.left == None and root.right == None:
#终于找到了子节点，添加一条path进去吧！
all_paths.append(tmp_result)
pass
if root.left != None:
findPath(root.left, tmp_result)
if root.right != None:
findPath(root.right, tmp_result)
return
tmp_result=''
if root != None:
findPath(root,tmp_result)
return all_paths
这个解法让我认识到，在递归的时候，传参是多么的重要！ 参数也可以累加的哦！