java beats 91% solution using DFS


  • 0
    E
    public int pathSum(TreeNode root, int sum) {
            // sanity check
            if (root == null) {
                return 0;
            }
            int[] res = new int[1];
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);
            findPath(root, sum, res, map, 0);
            return res[0];
            
        }
        
        private void findPath(TreeNode root, int sum, int[] res, Map<Integer, Integer> map, int prefixSum) {
            // base case
            if (root == null) {
                return; 
            }
            
            // recursive rule
            int temp = prefixSum + root.val;
            Integer value = map.get(temp - sum);
            if (value != null && value > 0) {
                res[0] += value;
            }
            map.put(temp, map.getOrDefault(temp, 0) + 1);
            findPath(root.left, sum, res, map, temp);
            findPath(root.right, sum, res, map, temp);
            map.put(temp, map.getOrDefault(temp, 1) - 1);
        }
    

Log in to reply
 

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