437. Path Sum III

题干简述：

给我们一个二叉树的根节点与一个目标值，求当前二叉树满足和为目标值的路径数目。

解题思路

这题实际上是 112. Path Sum 的变种，求解的思路也差不多，不过在递归的时候，需要区分包含该节点和不包含该节点的情况，并累计满足条件的路径数。

依旧是前序遍历递归求解，有兴趣可以参考我的这篇文章：112. Path Sum

重点在于为什么这里要拆分成两个递归函数，和 res 的算法。

拆分成两个递归函数是因为，我们这里在递归时，会有两种情况，包含根节点和不包含根节点。在包含根节点时，我们的路径数目，应该先判断当前节点自身是否等于目标值，再拆分为其左右子树的结果，将这三个值累加即可得到这个根节点对应的树的满足条件的路径的数目。在不包含根节点时，将其左右子树作为两个新的树进行统计；这里的流程是和之前是一致的。

题解

/**
 * 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}
 */
var pathSum = function(root, targetSum) {
    if (!root) return 0;
    let res = 0;
    
    res = getPaths(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    
    return res;
};

const getPaths = (node, target) => {
    if (!node) return 0;
    let ret = 0;
    if (node.val === target) {
        ret = 1;
    }
    ret = ret + getPaths(node.left, target - node.val) + getPaths(node.right, target - node.val);
    return ret;
}

Q.E.D.

Take it easy