题目
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
解题思路
判断从根节点到叶子节点的路径节点和是否等于目标值
- 定义全局变量hasSum用于记录是否有从根节点到叶子节点的路径节点和等于目标值
- 遍历所有root-to-leaf path，累加得到各路径的值，
- 如果和等于目标值，则将全局变量hasSum置为true
- 最后返回hasSum的值
注意
需要判断叶子节点，叶子节点的左右节点都为空
代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var hasSum bool
func addPathSum(t *TreeNode, sum, sumNow int) {
if t == nil {
return
}
val := t.Val
sumNow += val
if sum == sumNow && isLeaf(t){
hasSum = true
} else {
addPathSum(t.Left, sum, sumNow)
addPathSum(t.Right, sum, sumNow)
}
}
func isLeaf(t *TreeNode) bool {
if t != nil && t.Left ==nil && t.Right == nil {
return true
}
return false
}
func hasPathSum(root *TreeNode, sum int) bool {
hasSum = false
if root == nil {
return false
}
sumNow := root.Val
if isLeaf(root) && sum == sumNow {
hasSum = true
}
addPathSum(root.Left, sum, sumNow)
addPathSum(root.Right, sum, sumNow)
return hasSum
}
