题目描述#

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

这里的叶子节点指的是没有左右子节点的节点。只要存在任意一条满足条件的根到叶路径，就返回 true；如果所有路径都不满足，就返回 false。

思路#

这道题适合直接用递归处理。因为题目要求判断“从根到叶子”的路径是否满足条件，所以每到一个节点，都可以把当前节点的值从 targetSum 里减掉，表示后续路径还需要补上的和。

如果当前节点为空，说明这条路径走不通，直接返回 false。如果已经走到叶子节点，就说明路径已经完整，此时只需要判断减完之后的 targetSum 是否等于 0。等于 0 说明当前这条根到叶路径刚好满足题意。

如果当前节点还不是叶子节点，就继续递归判断左子树和右子树。只要任意一边存在满足条件的路径，结果就是 true。这份写法很直接，也正好对应题目本身的定义。

代码#

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	targetSum -= root.Val
	if root.Right == nil && root.Left == nil {
		return targetSum == 0 // 判断叶子节点是否满足
	}
	return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}