面试题 04.12. 求和路径

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paths-with-sum-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.HashMap;
import java.util.Map;

class Solution {

    private int ans = 0;

    private Map dp = new HashMap() {{
        put(0, 1);
    }};

    private void solve(TreeNode root, int sum, int target) {
        if (root == null) {
            return;
        }
        sum += root.val;
        int cnt = dp.getOrDefault(sum, 0);
        int need = sum - target;
        ans += dp.getOrDefault(need, 0);
        dp.put(sum, cnt + 1);
        solve(root.left, sum, target);
        solve(root.right, sum, target);
        if (cnt == 0) {
            dp.remove(sum);
        } else {
            dp.put(sum, cnt);
        }
    }

    public int pathSum(TreeNode root, int sum) {
        solve(root, 0, sum);
        return ans;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}