这篇文章给大家介绍怎样求python二叉树路径和,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回 true
, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2
。
解题思路:
1,对于二叉树类型题目一般都是递归解
2,递归有两种:自根向下和自叶子向上
3,对于相等类型题目和最大值题目解题思路相反,本题采用自根向下
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func hasPathSum(root *TreeNode, sum int) bool { if root==nil{ return false } if root.Left==nil && root.Right==nil{ return root.Val==sum } return hasPathSum(root.Left,sum-root.Val)||hasPathSum(root.Right,sum-root.Val)}
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5]]
思路:
1,同样是递归,需要每一次把走过的路径存下来传下去,如果满足条件就返回,否则舍弃
2,注意golang 传slice 和map的坑,虽然slice的len是每次传值,但是数据地址是一样的,所以会覆盖掉,每次数据结果都不一样
3,解决办法copy函数进行复制。
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func pathSum(root *TreeNode, sum int) [][]int { var r [][]int if root ==nil{ return r } var temp []int return walk(root,sum,temp)}func walk(root *TreeNode, sum int,temp1 []int)([][]int){ var r [][]int if root==nil{ return r } temp:=make([]int,len(temp1)) copy(temp,temp1) temp=append(temp,root.Val) //fmt.Println(root,temp,sum) if root.Left==nil && root.Right==nil{ if root.Val==sum{ r=append(r,temp) // fmt.Println(root,temp,sum,r) return r } return r } tl:=walk(root.Left,sum-root.Val,temp) tr:=walk(root.Right,sum-root.Val,temp) if len(tl)>0 { r=append(r,tl...) } if len(tr)>0 { r=append(r,tr...) } return r}
关于怎样求python二叉树路径和就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4586289/blog/4634779