akhayoon

Path Sum JS DFS

Sep 26th, 2021
740
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var pathSum = function(root, targetSum) {
  2.     let sumCount = new Map([[0, 1]]), ans = 0;
  3.  
  4.     const dfs = (root, prevSum) => {
  5.         if (root === null) return;
  6.         const sum = prevSum + root.val;
  7.  
  8.         ans += sumCount.get(sum - targetSum) || 0;
  9.         sumCount.set(sum, (sumCount.get(sum) || 0) + 1);
  10.  
  11.         dfs(root.left, sum);
  12.         dfs(root.right, sum);
  13.         sumCount.set(sum, sumCount.get(sum) - 1);
  14.     };
  15.    
  16.     dfs(root, 0);
  17.     return ans;
  18. };
RAW Paste Data