Go刷LeetCode系列：二叉树（3）二叉树路径和（golang 二叉树遍历）

Go刷LeetCode系列：二叉树（3）二叉树路径和（golang 二叉树遍历）

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 

给定如下二叉树，以及目标和 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

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。