vlambda博客
学习文章列表

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 = None
class 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存储到res if 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()
复杂度计算




运行结果