扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
如何解析python二叉树中的路径总和,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:申请域名、网站空间、营销软件、网站建设、阜康网站维护、网站推广。
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
解题思路:
1,此问题可以拆分成子问题:从根节点开始路径和等于某数的路径个数
2,将所有节点为根的个数和起来
3,以某节点为根的路径和包括多种情况
A,包括和为0的子路径
B,不包括
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, sum int) int {
count:=sumRoot(root,sum)
if root!=nil{
count+=pathSum(root.Left,sum)
count+=pathSum(root.Right,sum)
}
return count
}
func sumRoot(root*TreeNode,sum int)int{
if root==nil{
return 0
}
if root.Val==sum{
return 1 +sumRoot(root.Left,sum-root.Val)+sumRoot(root.Right,sum-root.Val)
}
return sumRoot(root.Left,sum-root.Val)+sumRoot(root.Right,sum-root.Val)
}
看完上述内容,你们掌握如何解析python二叉树中的路径总和的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流