Iterative post-order + prefix sum with explanation and pictures. Spent 2 days to learn post-order.
To solve this problem we can combine two techniques: post-order tree traversal and prefix sum.\n\n\nFor post-order, at first we going to the left (or to the rig
To solve this problem we can combine two techniques: post-order tree traversal and prefix sum.\n![image](https://assets.leetcode.com/users/images/52b1c3c7-2c4c-4bba-a20c-503fe861c74d_1656332451.4314165.png)\n\nFor post-order, at first we going to the left (or to the right if there is no left node) and bottom (until we find the leaf):\n![image](https://assets.leetcode.com/users/images/a07c9077-a7e9-4667-9240-07bc97f5f463_1656331565.2107663.png)\n\n```\nfunction postOrder(root: TreeNode): void {\n  let curr = root;\n\n  const stack = [];\n\n  while (stack.length || curr) {\n    // Going to the bottom\n    while (curr) {\n      stack.push(curr);\n\n      if (curr.left) {\n        curr = curr.left;\n      } else if (curr.right) {\n        curr = curr.right;\n      } else {\n        curr = null;\n      }\n    }\n\n    // the last unhandled node\n    const nPopped = stack.pop();\n\tcalcTreeNode(nPopped);\n\n    // if the current node is not left child of the latest node in stack\n    // than it means we already checked the right side\n\t// in other words - if the current node is the left child than we must go right\n    if (stack.length && stack[stack.length - 1].left == nPopped) {\n      curr = stack[stack.length - 1].right;\n    }\n  }\n}\n```\n![image](https://assets.leetcode.com/users/images/c8e71983-809d-4eef-bff9-04fd3a04bfdd_1656331914.2940583.png)\n\nNow, lets combine with prefix sum. While going to the bottom let\'s calculate our sum, count and count for the current sum. \n```\n      currentSumm += curr.val;\n      count += map.get(currentSumm - targetSum) ?? 0;\n      map.set(currentSumm, (map.get(currentSumm) ?? 0) + 1);\n```\nAlso, we must remember to backtrack the sum after we popped the node.\n```\n    map.set(currentSumm, map.get(currentSumm) - 1);\n    currentSumm -= nPopped.val;\n```\n\nFull code:\n```\nfunction pathSum(root: TreeNode | null, targetSum: number): number {\n  let curr = root;\n\n  const stack = [];\n\n  let currentSumm = 0;\n  const map = new Map();\n  map.set(0, 1);\n\n  let count = 0;\n\n  while (stack.length || curr) {\n    // Going to the leftmost bottom\n    while (curr) {\n      stack.push(curr);\n\n      //calculate summ, current count\n      currentSumm += curr.val;\n\n      count += map.get(currentSumm - targetSum) ?? 0;\n      map.set(currentSumm, (map.get(currentSumm) ?? 0) + 1);\n\n      if (curr.left) {\n        curr = curr.left;\n      } else if (curr.right) {\n        curr = curr.right;\n      } else {\n        curr = null;\n      }\n    }\n\n    const nPopped = stack.pop();\n\n    // Revert summ operations\n    map.set(currentSumm, map.get(currentSumm) - 1);\n    currentSumm -= nPopped.val;\n    //\n\n    // if the current node is not left child of the latest node in stack\n    // than it means we already checked the right side\n    if (stack.length && stack[stack.length - 1].left == nPopped) {\n      curr = stack[stack.length - 1].right;\n    }\n  }\n\n  return count;\n}\n```\n
['Iterator', 'TypeScript', 'JavaScript']