Java

import java.util.HashMap;

/**
 437	Path Sum III

 You are given a binary tree in which each node contains an integer value.

 Find the number of paths that sum to a given value.

 The path does not need to start or end at the root or a leaf,
 but it must go downwards (traveling only from parent nodes to child nodes).

 The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

 Example:

 root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

       10
      /  \
     5   -3
    / \    \
   3   2   11
  / \   \
 3  -2   1

 Return 3. The paths that sum to 8 are:

 1.  5 -> 3
 2.  5 -> 2 -> 1
 3. -3 -> 11

 @tag-tree
 */

public class Path_Sum_III {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */


    class Solution {

        public int pathSum(TreeNode root, int sum) {
            // 路径之和 => 其个数
            HashMap<Integer, Integer> preSum = new HashMap<>();

            // @note: initialiated to be 1, 当 curSum 等于 sum 的时候,表明从根结点到当前结点正好是一条符合要求的路径
            preSum.put(0,1);

            return helper(root, 0, sum, preSum);
        }

        public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
            if (root == null) {
                return 0;
            }

            currSum += root.val;
            int res = preSum.getOrDefault(currSum - target, 0);

            // add before pass down as prevSum
            preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

            res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);

            // restore, since it's not prevSum when returning to upper recursion
            preSum.put(currSum, preSum.get(currSum) - 1);

            return res;
        }
    }
}

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null)
            return 0;
        return paths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int paths(TreeNode root, int sum) {
        if (root == null)
            return 0;
        int paths = 0;
        if (root.val == sum)
            paths++;
        paths += paths(root.left, sum - root.val);
        paths += paths(root.right, sum - root.val);
        return paths;
    }
}

All Problems

All Solutions