Time: 2019-08-12
题目描述
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/
2 3
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
用分治法 + 递归来求解，注意本题的递归出口包含叶子结点。
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 1.递归的定义：求出以root为根的所有路径
def binaryTreePaths(self, root: TreeNode) -> List[str]:
paths = []
# 3.递归的出口
if root == None:
return paths
# 叶子结点需要单独处理
if root.left == None and root.right == None:
paths.append(str(root.val))
return paths
# 2.递归的拆解
leftPaths = self.binaryTreePaths(root.left)
rightPaths = self.binaryTreePaths(root.right)
# 合并
for path in leftPaths:
paths.append(str(root.val) + '->' + path)
for path in rightPaths:
paths.append(str(root.val) + '->' + path)
return paths
END.
