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;
        }
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Long, Integer> cnt = new HashMap<>();
    private int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        cnt.put(0L, 1);
        this.targetSum = targetSum;
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, long s) {
        if (node == null) {
            return 0;
        }
        s += node.val;
        int ans = cnt.getOrDefault(s - targetSum, 0);
        cnt.merge(s, 1, Integer::sum);
        ans += dfs(node.left, s);
        ans += dfs(node.right, s);
        cnt.merge(s, -1, Integer::sum);
        return ans;
    }
}

// OJ: https://leetcode.com/problems/path-sum-iii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    int ans = 0;
    unordered_map<int, int> dfs(TreeNode *root, int sum) { // map of sums from the current node to a child node
        if (!root) return {};
        unordered_map<int, int> m{ {root->val, 1} };
        auto left = dfs(root->left, sum), right = dfs(root->right, sum);
        for (auto &[val, cnt] : left) m[val + root->val] += cnt;
        for (auto &[val, cnt] : right) m[val + root->val] += cnt;
        if (m.count(sum)) ans += m[sum];
        return m;
    }
public:
    int pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def dfs(node, s):
            if node is None:
                return 0
            s += node.val
            ans = cnt[s - targetSum]
            cnt[s] += 1
            ans += dfs(node.left, s)
            ans += dfs(node.right, s)
            cnt[s] -= 1
            return ans

        cnt = Counter({0: 1})
        return dfs(root, 0)

############

class Solution(object):
  def pathSum(self, root, target):
    """
    :type root: TreeNode
    :type target: int
    :rtype: int
    """
    self.count = 0
    preDict = {0: 1}

    def dfs(p, target, pathSum, preDict):
      if p:
        pathSum += p.val
        self.count += preDict.get(pathSum - target, 0)
        preDict[pathSum] = preDict.get(pathSum, 0) + 1
        dfs(p.left, target, pathSum, preDict)
        dfs(p.right, target, pathSum, preDict)
        preDict[pathSum] -= 1

    dfs(root, target, 0, preDict)
    return self.count

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
	cnt := map[int]int{0: 1}
	var dfs func(*TreeNode, int) int
	dfs = func(node *TreeNode, s int) int {
		if node == nil {
			return 0
		}
		s += node.Val
		ans := cnt[s-targetSum]
		cnt[s]++
		ans += dfs(node.Left, s) + dfs(node.Right, s)
		cnt[s]--
		return ans
	}
	return dfs(root, 0)
}

/**
 * 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;
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Long, Integer> cnt = new HashMap<>();
    private int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        cnt.put(0L, 1);
        this.targetSum = targetSum;
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, long s) {
        if (node == null) {
            return 0;
        }
        s += node.val;
        int ans = cnt.getOrDefault(s - targetSum, 0);
        cnt.merge(s, 1, Integer::sum);
        ans += dfs(node.left, s);
        ans += dfs(node.right, s);
        cnt.merge(s, -1, Integer::sum);
        return ans;
    }
}

// OJ: https://leetcode.com/problems/path-sum-iii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    int ans = 0;
    unordered_map<int, int> dfs(TreeNode *root, int sum) { // map of sums from the current node to a child node
        if (!root) return {};
        unordered_map<int, int> m{ {root->val, 1} };
        auto left = dfs(root->left, sum), right = dfs(root->right, sum);
        for (auto &[val, cnt] : left) m[val + root->val] += cnt;
        for (auto &[val, cnt] : right) m[val + root->val] += cnt;
        if (m.count(sum)) ans += m[sum];
        return m;
    }
public:
    int pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def dfs(node, s):
            if node is None:
                return 0
            s += node.val
            ans = cnt[s - targetSum]
            cnt[s] += 1
            ans += dfs(node.left, s)
            ans += dfs(node.right, s)
            cnt[s] -= 1
            return ans

        cnt = Counter({0: 1})
        return dfs(root, 0)

############

class Solution(object):
  def pathSum(self, root, target):
    """
    :type root: TreeNode
    :type target: int
    :rtype: int
    """
    self.count = 0
    preDict = {0: 1}

    def dfs(p, target, pathSum, preDict):
      if p:
        pathSum += p.val
        self.count += preDict.get(pathSum - target, 0)
        preDict[pathSum] = preDict.get(pathSum, 0) + 1
        dfs(p.left, target, pathSum, preDict)
        dfs(p.right, target, pathSum, preDict)
        preDict[pathSum] -= 1

    dfs(root, target, 0, preDict)
    return self.count

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
	cnt := map[int]int{0: 1}
	var dfs func(*TreeNode, int) int
	dfs = func(node *TreeNode, s int) int {
		if node == nil {
			return 0
		}
		s += node.Val
		ans := cnt[s-targetSum]
		cnt[s]++
		ans += dfs(node.Left, s) + dfs(node.Right, s)
		cnt[s]--
		return ans
	}
	return dfs(root, 0)
}

437 - Path Sum III

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions