package pathsum

import . "gitee.com/dllearn/geektime-algorithm-learn/structures"

// 112. 路径总和
// https://leetcode-cn.com/problems/path-sum/

// 这题我一开始理解错了，以为只要找到一个路径相加 = targetSum 就行
// 其实一定要到 叶子节点 && 相加 = targetSum ，两个条件

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

func dfs(node *TreeNode, targetSum int, preVal int) bool {
	if node == nil {
		return false
	}
	if node.Val+preVal == targetSum && node.Left == nil && node.Right == nil {
		return true
	}
	preVal = node.Val + preVal
	is := dfs(node.Left, targetSum, preVal)
	if is {
		return is
	}
	is = dfs(node.Right, targetSum, preVal)
	if is {
		return is
	}
	return false
}