• 题目

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

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：

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

1. 两次深度优先搜索

一次dfs是只能从一个头结点往下搜索符合情况，但是这道题路径不需要从根节点开始，也不需要在叶子节点结束，可以考虑使用两次dfs
两次dfs无非就是让每个节点都当一次头结点，然后以他们为根向下搜索可行情况，但是时间复杂度也会上升到O(N2)

代码如下：

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, int targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}

1. dfs＋前缀和＋hashmap＋回溯

   • dfs：dfs为解题总体思路，从上至下
   • 前缀和：当遍历到10节点时，前缀和就为10，往下到5节点，则前缀和为15，如果两个节点前缀和相减等于targetSum，说明这两个节点之间就有符合的路径
   • hashmap：用来记录前缀和的容器，注意：由于节点前缀和是可能重复的，所以如果一个节点它与上面两个节点相减为targetSum，则应该是有两条符合的路径，因此map的value还要记录结点前缀和出现次数
   • 回溯：当该节点即它的左右子树都已经判断完了，就应该在map中删除一次(－1而不是remove)该节点的前缀和,防止该前缀和与其他分支的前缀和冲突

代码如下：