第10题力扣LeetCode 热题 HOT 100(437. 路径总和)

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

题解

思路其实很简单，二叉树中某个路径的总和为targetSum值，可以通过一个数组来记录一颗树种到某个节点所经历节点的节点值。

以某个节点为例，如果存在二叉树中存在一条路径，路径末尾节点为该节点，意味着，数组中连续的节点值（即路径）加起来恰好构成targetSum 值。

以此，每到一个节点，把节点值加入数组中，当递归调用左右节点值后，从数组中除去这个节点值（回溯）因为该节点已经不是递归遍历中下个节点中的经过的结点。

/**
 * 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 {number}
 */
// let sum = 0;

var pathSum = function(root, targetSum) {
   	let sum = 0
   
    let find = function(root, arr, targetSum){
    if(!root) return ;
    arr.push(root.val);
    let val = 0;
    // 先求路径结点总和， 下面还有一个for循环为 总和减去路径中最早的结点值，依次求出每个结点值到路径末尾的值。
    for(let i = 0; i< arr.length; i++){
        val = val+ arr[i]
    }
       
    if(val == targetSum) sum++;
    for(let i = 0; i <arr.length-1; i++){
        val = val- arr[i];
        if(val == targetSum) sum++;
    }
    find(root.left, arr, targetSum);
    find(root.right, arr, targetSum);
    arr.pop();
    return;
}
    find(root, [], targetSum);
    return sum;
};