112_path_sum

112. 路径总和 简单

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

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

提示：

• 树中节点的数目在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

代码参考：

package main

import "fmt"

func main() {
    tree := &Tree{}
    tree.root = &TreeNode{Val: 5}
    tree.root.Left = &TreeNode{Val: 4}
    tree.root.Right = &TreeNode{Val: 8}
    fmt.Println(hasPathSum(tree.root, 13)) // true
}

func hasPathSum(root *TreeNode, sum int) bool {
    var sums []int
    traverse(root, &sums)
    for _, v := range sums {
        if v == sum {
            return true
        }
    }
    return false
}

// 遍历将父节点的值存储到子节点中
// 若是叶子节点则算作一个 sum
func traverse(root *TreeNode, sums *[]int) {
    if root == nil {
        return
    }

    // 叶子节点
    if root.Left == nil && root.Right == nil {
        *sums = append(*sums, root.Val) // bingo
    }
    if root.Left != nil {
        root.Left.Val += root.Val
    }
    if root.Right != nil {
        root.Right.Val += root.Val
    }
    traverse(root.Left, sums)
    traverse(root.Right, sums)
}