O(n^2), prefix sum - O(n)


  • 1
    A

    Lets consider any path starting from root till leaf as a sequence. Now we have an array of integer values. We need to calculate number of sums (a[i] + a[i+1] + ... + a[j], i<j) which will be equal to a target. We can do it by fixing two positions for N^2.

    public class Solution {
        
        public int pathSum(TreeNode root, int sum) {
            if (root==null) {
                return 0;
            }
            
            int childSum = pathSum(root.left, sum) + pathSum(root.right, sum);
            return suffixPathSum(root, 0, sum) + childSum;
        }
        
        private int suffixPathSum(TreeNode node, int curSum, int target) {
            if (node==null) {
                return 0;
            }
            
            int cnt = 0;
            if (curSum+node.val==target) {
                cnt++;
            }
            
            cnt += suffixPathSum(node.left, curSum+node.val, target);
            cnt += suffixPathSum(node.right, curSum+node.val, target);
            
            return cnt;
        }
    }
    

    O(n) solution. Lets calculate prefix sum for each position.
    We know that prefixSum - target = X. Now its enough to know how many times prefix sum with value X was meet till this position. For storing that we can use map.

    
    public class Solution {
        
        public int pathSum(TreeNode root, int sum) {
            HashMap<Integer, Integer> prefSumCounter = new HashMap<>();
            prefSumCounter.put(0,1);
            return calculatePrefSum(root, 0, sum, prefSumCounter);
        }
        
        private int calculatePrefSum(TreeNode node, int prefSum, int target, HashMap<Integer, Integer> prefSumCounter) {
            if (node==null) return 0;
            int nSum = prefSum+node.val;
            
            int x = nSum-target;
            int counter = prefSumCounter.getOrDefault(x,0);
            
            prefSumCounter.putIfAbsent(nSum, 0);
            prefSumCounter.put(nSum, prefSumCounter.get(nSum)+1);
            
            counter += calculatePrefSum(node.left, nSum, target, prefSumCounter);
            counter += calculatePrefSum(node.right, nSum, target, prefSumCounter);
            
            prefSumCounter.put(nSum, prefSumCounter.get(nSum)-1);
            if (prefSumCounter.get(nSum)<=0) prefSumCounter.remove(nSum);
            
            return counter;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.