257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
题目解析
题目解答
方法：回溯法
介绍：
这道题需要存储 所有路径，
所以该问题的终止条件是当 root 到达 叶子节点的时候，
将当前路径存储到res中【关键点：终止条件的选择】
代码展示
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def binaryTreePaths(self, root: TreeNode) -> List[str]:'''方法：回溯法介绍：这道题需要存储 所有路径，所以该问题的终止条件是当 root 到达 叶子节点的时候，将当前路径存储到res中【关键点：终止条件的选择】'''res = []if root:self.dfs(root,[],res)return res# 功能：回溯函数def dfs(self,root,path,res):# step 1：入队：将 当前元素 入队path.append(str(root.val))# step 2：判断终止条件：当root为叶子节点，将当前路径path存储到resif not root.left and not root.right:res.append("->".join(path))# step 3：向做if root.left:self.dfs(root.left,path,res)# step 4：向右if root.right:self.dfs(root.right,path,res)path.pop()
复杂度计算
运行结果