这篇文章给大家介绍如何分析python二叉树中和为某一值的路径,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示:
节点总数 <= 10000
注意:本题与主站 113 题相同:https://leetcode-cn.com/problems/path-sum-ii/
解题思路:
1,此题只是,先序遍历的一个变形
2,递归执行,深度优先遍历,这个时候sum变为sum-root.Val
3,到达叶子节点的时候,判断sum==root.Val,是则将整个链路加入结果里,否则,继续遍历
4,需要注意一点了,go的slice传递的是值,但是数据引用的是同一份
5,copy的时候需要先make分配空间,否则copy不成功
代码实现
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, sum int) [][]int {
var p[]int
var r [][]int
r=dfs(root,sum,p,r)
return r
}
func dfs(root *TreeNode, sum int,path []int,ret [][]int)[][]int{
if root==nil {
return ret
}
path=append(path,root.Val)
if root.Left==nil && root.Right==nil {
if sum==root.Val{
p:=make([]int,len(path))
copy(p,path)
ret=append(ret,p)
fmt.Println(1,":",path,p,sum,root,ret)
}
return ret
}
if root.Left==nil{
return dfs(root.Right,sum-root.Val,path,ret)
}
if root.Right==nil{
return dfs(root.Left,sum-root.Val,path,ret)
}
l:=dfs(root.Left,sum-root.Val,path,ret)
r:=dfs(root.Right,sum-root.Val,path,ret)
fmt.Println(ret,l,r)
ret=append(ret,l...)
ret=append(ret,r...)
return ret
}
关于如何分析python二叉树中和为某一值的路径就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。