題號(hào) 112/113/437

pathsum III ：http://www.itdecent.cn/p/400586f0a7c9

import java.util.*;

public class PathSum {

    /**
     *
     * pathSum：root --> leaf：看有沒有加起來 == sum的路徑
     *
     * dfs
     * */
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) {
            return false;
        }

        if(root.left == null && root.right == null && sum == root.val) {
            return true;
        }

        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }


    /**
     * pathSum ii：root --> leaf：返回所有 加起來 == sum的路徑
     *
     * 回溯
     * */
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> solution = new ArrayList<>();

        findSum(res, solution, root, sum);

        return res;
    }

    private void findSum(List<List<Integer>> result, List<Integer> solution, TreeNode root, int residual){
        if (root == null) {
            return;
        }

        residual -= root.val;
        solution.add(root.val);
        // 這里有必要解釋下為什么不把這個(gè)條件和上一個(gè)條件合并
        // 以 root==null，且 residual == root.val 作為終點(diǎn)；
        // 因?yàn)檫@么寫，左右子樹會(huì)各來一遍，result會(huì)加入兩遍solution
        if (residual == 0 && root.left == null && root.right == null) {

            result.add(new ArrayList<>(solution));
        }

        findSum(result, solution, root.left, residual);
        findSum(result, solution, root.right, residual);
        solution.remove(solution.size()-1);
    }


    /**
     *
     * pathSum iii：只要路徑向下即可，不要求起終點(diǎn)為root和leaf：返回看加起來 == sum的路徑的個(gè)數(shù)
     *
     * 前綴和
     */
    public int pathSumIII(TreeNode root, int target) {
        if(root == null) {
            return 0;
        }

        Map<Integer, Integer> prefix = new HashMap<>();
        prefix.put(0, 1);

        return helper(root, target, prefix, 0);
    }

    private int helper(TreeNode root, int target, Map<Integer, Integer> prefix, int curSum) {
        if(root == null) {
            return 0;
        }

        int res = 0;
        curSum += root.val;

        // 此前存在路徑的個(gè)數(shù)（A點(diǎn) 和 當(dāng)前點(diǎn) 的差值是target，那么 A-當(dāng)前點(diǎn)是有效路徑）
        res += prefix.getOrDefault(curSum-target, 0);

        // 回溯
        prefix.put(curSum, prefix.getOrDefault(curSum, 0) + 1);
        res += helper(root.left, target, prefix, curSum);
        res += helper(root.right, target, prefix, curSum);
        prefix.put(curSum, prefix.getOrDefault(curSum, 0) - 1);

        return res;
    }

}