怎样求python二叉树路径和
发表于:2024-10-12 作者:千家信息网编辑
千家信息网最后更新 2024年10月12日,这篇文章给大家介绍怎样求python二叉树路径和,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有
千家信息网最后更新 2024年10月12日怎样求python二叉树路径和
这篇文章给大家介绍怎样求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二叉树路径和就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
节点
路径
目标
叶子
思路
题目
递归
内容
数据
更多
示例
类型
帮助
不错
最大
兴趣
函数
办法
地址
小伙
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
上海软件开发服务创意
连接另一个电脑的数据库
csgo怎么改服务器最流畅
森科网络技术
n11数据库出现乱码
本地mysql数据库修改字符
数据库大作业实验心得体会
数据库安全等级保护证明
视频数据平台服务器
查看管家婆数据库密码
hdg8服务器耗电量
企业网络安全性怎么样
网络安全管理软件安装证明
非主流图片素材软件开发
北京推广软件开发公司官网
建立空间数据库需要创建哪些表
股价提醒软件开发
湛江软件开发订制
公民个人信息 网络安全法
互联网大厂跳槽金融科技
深圳安卓应用软件开发公司有哪些
单位服务器有临时文件进不去
数据库上传图片
南昌纯真软件开发有限公司官网
新华互联网科技全国直营院校
最新免费服务器节点
宁德软件开发培训学校
中电36软件开发
网络安全宣传员工作内容
删数据库实例