leetcode_257. 二叉树的所有路径
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1 / \ 2 3 \ 5
输出: ["1->...
目录
一、题目内容
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
二、解题思路
回溯+DFS,简单易懂
三、代码
# 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):
paths = []
if root is None:
return []
def dfs(root, path):
if root.left is None and root.right is None:
paths.append(path)
return
if root.left is not None:
org_path = path
path += "->" + str(root.left.val)
dfs(root.left, path)
path = org_path
if root.right is not None:
org_path = path
path += "->" + str(root.right.val)
dfs(root.right, path)
path = org_path
dfs(root, str(root.val))
return paths
if __name__ == '__main__':
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(5)
s = Solution()
ans = s.binaryTreePaths(root=root)
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108400545
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)