package main

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

// important!! "leaf node"
func hasPathSumIter(root *TreeNode, sum int, tmpSum int) bool {
	if root.Left == nil && root.Right == nil {
		return tmpSum+root.Val == sum
	}
	if root.Left == nil {
		return hasPathSumIter(root.Right, sum, tmpSum+root.Val)
	}
	if root.Right == nil {
		return hasPathSumIter(root.Left, sum, tmpSum+root.Val)
	}
	return hasPathSumIter(root.Left, sum, tmpSum+root.Val) || hasPathSumIter(root.Right, sum, tmpSum+root.Val)
}

/**
 * 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
	}
	return hasPathSumIter(root, sum, 0)
}

// func main() {
// 	/**
// 	 * t1:  5
// 	 *     / \
// 	 *    1   4
// 	 *       / \
// 	 *      2   3
// 	 */
// 	t1r := TreeNode{4, nil, nil}
// 	t1 := &TreeNode{5, nil, &t1r}
// 	fmt.Println(hasPathSum(t1, 11))
// 	fmt.Println(hasPathSum(t1, 5))
// 	fmt.Println(hasPathSum(t1, 7))
// 	fmt.Println(hasPathSum(nil, 0))
// }