给你一个二叉树的根节点 root ，按任意顺序 ，返回所有从根节点到叶子节点的路径。

示例 1：

输入：root = [1,2,3,null,5]

输出：["1->2->5","1->3"]

1

/ \

2 3

\

5

示例 2：

输入：root = [1]

输出：["1"]

题目链接：https://leetcode.cn/problems/binary-tree-paths

1. 深度优先搜索

定义一个函数，使用递归，如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归；

如果当前节点是叶子节点，则在当前路径末尾添加该节点，将该路径加入路径列表。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:paths = []def form_path(root,path):if root:path += str(root.val)#如果是叶子节点，添加路径if not root.left and not root.right:paths.append(path)else:#不是叶子节点，继续递归path += '->'form_path(root.left,path)form_path(root.right,path)form_path(root,'')return paths

2. 广度优先搜索

与层序遍历类似，使用队列。区别是记录节点的同时记录路径，需要使用两个队列。

层序遍历参考 -> 二叉树的遍历 https://blog.csdn.net/wy_hhxx/article/details/128566355

循环取出节点队列的首节点，如果它是叶子节点，则将它对应的路径加入到答案中；

如果它不是叶子节点，则将它的孩子节点和路径分别加入到两个队列。

当节点队列为空时（路径队列此时也为空）广度优先搜索结束。

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:paths = []if not root:return pathsnode_queue = [root]path_queue = [str(root.val)]while node_queue:node = node_queue.pop(0)path = path_queue.pop(0)if not node.left and not node.right:paths.append(path)else:if node.left:node_queue.append(node.left)path_queue.append(path + '->' + str(node.left.val))if node.right:node_queue.append(node.right)path_queue.append(path + '->' + str(node.right.val))return paths