路径总和

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    // 如果当前节点是叶子节点，判断路径上的和是否等于目标和
    if root.Left == nil && root.Right == nil {
        return targetSum == root.Val
    }

    // 递归判断左右子树是否存在路径满足条件
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

func main() {
    // 创建一个二叉树
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 11}
    root.Left.Left.Left = &TreeNode{Val: 7}
    root.Left.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 13}
    root.Right.Right = &TreeNode{Val: 4}
    root.Right.Right.Right = &TreeNode{Val: 1}

    // 设定目标和
    targetSum := 22

    // 判断是否存在路径满足条件
    result := hasPathSum(root, targetSum)

    // 输出结果
    fmt.Printf("是否存在路径和为 %d 的路径: %v\n", targetSum, result)
}