路径总和 III

[JesseZhao1990]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    if(root === null) return 0;
    
    var res = findPath(root,sum);
    res += pathSum(root.left,sum);
    res += pathSum(root.right,sum);   
    return res;
    
};

function findPath(node,sum){
    if(node === null) return 0;
    var res = 0;
    if(sum - node.val === 0) res += 1;
    res += findPath(node.left,sum-node.val);
    res += findPath(node.right,sum-node.val)
    return  res;
}

解题思路

我们遍历整个树的过程中，对于每个节点来说，我们可以这样思考
在从这个节点往下走的路径中，有可能是包含此节点的值的和满足sum，
也有可能是不包含此节点的值的和满足sum

因此，我们的代码可以这样设计

var pathSum = function(root, sum) {
    if(root === null) return 0;
    
    // 包含本节点的值的和为sum的情况
    var res = findPath(root,sum);  
    
    // 不包含本节点的值的和为sum的情况
    res += pathSum(root.left,sum);
    res += pathSum(root.right,sum);  

    // 返回的是上边两种情况的和
    return res;
    
};

findPath的作用是找到包含此节点的值的情况。问题成功缩小到了寻找包含根节点的路径的和等于给定数值的路径数目，这样就简单了许多。我们在往下找的过程中。走一步减一下本节点的值，直到某一个节点的时候减去本节点的值之后正好等于零，说明我们找到了一条。

因此findPath应该这样设计。

function findPath(node,sum){
    if(node === null) return 0;
    var res = 0;
    if(sum - node.val === 0) res += 1;
    res += findPath(node.left,sum-node.val);
    res += findPath(node.right,sum-node.val)
    return  res;
}

leetcode原题地址：https://leetcode-cn.com/problems/path-sum-iii/description/