当前位置: 首页 > 后端技术 > Python

力扣-0257.二叉树的所有路径Paths二叉树[Python]

时间:2023-03-26 11:53:14 Python

LeetCode0257.二叉树的所有路径Paths二叉树[Easy][Python][DFS]ProblemLeetCode给定一棵二叉树,返回所有根到叶的路径。注意:叶子是没有子节点的节点。示例:输入:1/\23\5输出:["1->2->5","1->3"]解释:所有根到叶子的路径分别是:1->2->5、1->3问题链接给定一棵二叉树,返回从根节点到叶节点的所有路径。解释:叶节点是指没有子节点的节点。示例:输入:1/\23\5输出:["1->2->5","1->3"]解释:所有根节点到叶节点的路径为:1->2->5、1->3思路DFS递归模板题。先访问根节点,然后分别判断左右子树。如果是叶子节点,则保存在ans中,如果不是,则将其添加到路径中,继续访问,直到到达叶子节点。Python3代码#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案:defbinaryTreePaths(self,root:TreeNode)->List[str]:如果不是root:return[]ans=[]self.dfs(root,ans,''+str(root.val))returnansdefdfs(self,root,ans,path):如果root.left==None和root.right==None:ans.append(path)如果root.left!=None:self.dfs(root.left,ans,path+'->'+str(root.left.val))ifroot.right!=None:self.dfs(root.right,ans,path+'->'+str(root.right.val))代码地址GitHub链接