257. 二叉树的所有路径
题目
给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
例：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
方法：递归
因为要求二叉树的所有路径，那么需要使用前序遍历
主要部分：
- path 用于记录一条路径，字符串形式
- result 用于记录所有路径，列表形式
- 若根节点为空，那么返回空列表
- 通过递归实现对路径的记录，最后输出路径的所有可能
递归部分：实现对每一条路径的记录
- 将节点的值以字符串的形式存入路径中
- 若此时的节点为叶子节点，那么之前的 path 已经完成，将其存入 result 中
- 若此时的节点不为叶子节点，即存在左子树或右子树，那么继续调用函数
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def binaryTreePaths(self, root):
path = ''
result = []
if root == None:
return
self.traversal(root, path, result)
return result
def traversal(self, node, path, result):
path += str(node.val)
if node.left == None and node.right == None:
result.append(path)
if node.left:
self.traversal(node.left, path + '->', result)
if node.right:
self.traversal(node.right, path + '->', result)
※ 回溯：
所以我们在进行调用 traversal 函数时，path 部分使用的是 path + ‘->’，而非提前将 path = path + '->'。若是提前进行赋值，那么在之后我们需要将末尾的 '->' 使用 pop 弹出，否则会导致多个 '->'
例：
root = [1,2,3,null,5]
第一次调用 traversal：
初始：根节点为 1，path = ''， result = []
过程：path = '1'
因为存在左子树，调用 traversal：
初始：根节点为 2，path = '1->'，result = []
过程：path = '1->2，继续调用...'
因为存在右子树，调用 traversal：
初始：根节点为 3，path = '1->'，result = []
过程：path = '1->3'
相关知识
-
str(object)：
str()
返回对象的字符串形式
