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

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

All Problems

All Solutions