LeetCode-112-路径总和

一：题目描述：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

二：示例与提示

示例 1:

1
2
3

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2:

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

1
2
3

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示:

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

三：思路

`深度优先搜索`

targetsum是总和，每次遍历节点时候减去当前节点的值，当遍历到叶子节点时候，如果targetsum减到0，就说明存在一条路径符合该路径上的值全加起来等于targetSum
在每次递归调用时，首先检查终止条件。当遍历到叶子节点时，如果目标和正好为0，则说明找到了符合条件的路径，返回true；否则，返回false
如果当前节点不是叶子节点，需要继续向下递归遍历。首先对左子树调用isPath函数，传递的目标和为targetSum - root.left.val（减去当前节点值）。如果返回值为true，则说明在左子树中找到了符合条件的路径，直接返回true。否则，继续对右子树调用isPath函数，传递的目标和为targetSum - root.right.val（减去当前节点值）。如果返回值为true，则说明在右子树中找到了符合条件的路径，直接返回true。
如果左右子树都没有找到符合条件的路径，则返回false。
最后，主函数hasPathSum首先检查根节点是否为空，如果为空则直接返回false。否则，通过调用isPath函数，传递的目标和为targetSum - root.val（减去根节点值），判断是否存在符合条件的路径。

四：代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    //后序遍历
    const isPath = (root, targetSum) => {
        //终止条件
        //当遍历到叶子节点时候同时目标值为0 就找到对应的路径
        if(!root.left && !root.right && targetSum === 0) return true
        //当遍历到叶子节点时，目标值不为0 则不是返回false
        if(!root.left && !root.right &&  targetSum !== 0) return false

        //如果是true才层层返回
        if(root.left && isPath(root.left, targetSum - root.left.val)) return true
        if(root.right && isPath(root.right, targetSum - root.right.val)) return true

        return false
    }
    if(!root) return false
    return isPath(root, targetSum - root.val)
};