建站
咨询
售后
建站咨询
怎样求python二叉树路径和
这篇文章给大家介绍怎样求python二叉树路径和，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。
成都创新互联主要从事成都做网站、网站建设、外贸营销网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务呼伦贝尔,10多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 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 [][]intif root ==nil{return r}var temp []intreturn walk(root,sum,temp)}func walk(root *TreeNode, sum int,temp1 []int)([][]int){var r [][]intif 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二叉树路径和就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
分享名称：怎样求python二叉树路径和
文章起源：http://lswzjz.com/article/gjhhic.html
