题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
分析
1）使用深度优先遍历的方式遍历二叉树。
2）通过计数器做减法-1的方式判断是否找到，当减为0且此时为叶子结点表示找到返回true，否则返回false。一旦找到就立刻返回true。
3）因为终止条件是判断叶子节点，所以递归的过程中需要判断，不要让空节点进入递归。
4）应有回溯操作，target-node.left.val的target数值没有改变，实现回溯。
代码
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if(!root) return false
function Count(node, target){
// 叶子节点判断
if(!node.left && !node.right && target===0) return true
if(!node.left && !node.right) return false
if(node.left){
if(Count(node.left, target-node.left.val)) return true
}
if(node.right){
if(Count(node.right, target-node.right.val)) return true
}
// 排除true的情况
return false
}
return Count(root, targetSum-root.val)
};
