image.png
image.png

解法

深度优先遍历，粗暴解法，计算每个节点向下所有满足目标和的路径，时间复杂度为O(N*N)

class Solution {

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

        int ret = dfs(root, targetSum);    
        // 每一个节点都作为起点算一下，先序遍历
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    /**
     * 深度优先遍历，获取每一个节点下可能的总数
     */
    public int dfs(TreeNode node, int targetSum) {
        int res = 0;
        if (node == null) {
            return res;
        }
        if (targetSum == node.val) {
            res++;
        }
        res += dfs(node.left, targetSum - node.val);
        res += dfs(node.right, targetSum - node.val);
        return res;
    } 
}

前缀和解法，时间复杂度为O(N)

class Solution {

    public int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> prefix = new HashMap<>();
        prefix.put(0, 1);
        int ret = dfs(root, prefix, 0, targetSum);   
        return ret;
    }

    /**
     * 前缀和解法
     */
    public int dfs(TreeNode node, Map<Integer, Integer> prefix, int cur, int targetSum) {
        if (node == null) {
            return 0;
        }
        // 根节点到当前节点的路径和
        cur = cur + node.val;
        // 计算有几个cur-targetSum的值，就代表有几个点能到当前节点是targetSum
        int ret = prefix.getOrDefault(cur - targetSum, 0);
        prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
        ret += dfs(node.left, prefix, cur, targetSum);
        ret += dfs(node.right, prefix, cur, targetSum);
        // 该分支已经走完，要回撤prefix中，因为走另一分支时，并不会有这个结果
        prefix.put(cur, prefix.getOrDefault(cur, 0) - 1);
        return ret;
    } 
}