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

/**
     * 前缀和
     */
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
//        当 targetSum 等于某个前缀和时，currPrefix - target = 0，当前节点自己就算做一条符合条件的路径，所以也要计数
        map.put(0L, 1);
        return preorder(root, map, targetSum, 0);
    }

    private int preorder(TreeNode node, Map<Long, Integer> map, int target, long currPrefix) {
        if (node == null) {
            return 0;
        }
        int num = 0;
//        当前前缀和
        currPrefix += node.val;
//        假设当前从根节点 root 到节点 node 的前缀和为 currPrefix
//        则在已保存的 前缀和 中查找是否存在 前缀和 刚好等于 currPrefix − target
//        假设从根节点 root 到节点 node 的路径中存在节点 P(i)，到根节点 root 的前缀和为 currPrefix − target
//        则节点 P(i+1) 到 node 的路径上所有节点的和一定为 target
//                1
//               /
//              2
//             /
//            3
//           /
//          4
//        给定值为 target = 5
//        prefix(3) = 1 + 2 + 3 = 6
//        prefix(1) = 1
//        假设 currPrefix = prefix(3) = 6 即 node = 3
//        currPrefix - target = 1 = prefix(1) 即 P(1) , 已经在 map 中，value = 1
//        因此 num = 1 , P(1 + 1) = P(2) 到 P(3) 的路径和为 target = 5
        num += map.getOrDefault(currPrefix - target, 0);
//        当前前缀和数量 + 1
        map.put(currPrefix, map.getOrDefault(currPrefix, 0) + 1);
        num += preorder(node.left, map, target, currPrefix);
        num += preorder(node.right, map, target, currPrefix);
//        回溯，防止左边前缀树影响右边前缀树，因为当前节点的前缀和只对子节点有效
//        当前节点可能为父节点的左子节点，切换到父节点的右子节点后左子节点的数据不应当被采用
        map.put(currPrefix, map.getOrDefault(currPrefix, 0) - 1);
        return num;
    }

/**
     * 一个朴素的做法是搜索以 每个节点 为根的（往下的）所有路径，并对路径总和为 targetSum 的路径进行累加统计
     * 在 pathSum2 中搜索所有节点，复杂度为 O(n)
     * 在 pathSum2 中对当前节点，使用 dfs 搜索以其为根的所有（往下的）路径，同时累加路径总和为 targetSum 的所有路径，复杂度为 O(n)
     */
    public int pathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
//        对当前节点深搜，获取符合条件的路径和
        var num = dfs(root, targetSum);
//        搜索所有节点，累加路径和
        num += pathSum2(root.left, targetSum);
        num += pathSum2(root.right, targetSum);
        return num;
    }

    private int dfs(TreeNode node, long targetSum) {
        if (node == null) {
            return 0;
        }
        int num = 0;
        if (node.val == targetSum) {
            num++;
        }
        num += dfs(node.left, targetSum - node.val);
        num += dfs(node.right, targetSum - node.val);
        return num;
    }