Five solutions. Beats 98%
Approach\nFive different approaches to solving the problem. From O(ndepth) to O(n) time. Best beats 98%.\n\n\n# Complexity\n- Time complexity: O(ndepth) - O(n)\
# Approach\nFive different approaches to solving the problem. From $$O(n*depth)$$ to $$O(n)$$ time. Best beats 98%.\n![1.png](https://assets.leetcode.com/users/images/04ce8bf5-51fa-4b6f-91e1-ce66ca66d15a_1727083562.2751834.png)\n\n# Complexity\n- Time complexity: $$O(n*depth)$$ - $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(depth)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Stack + Array $$O(n*depth)$$ Beats 95%.\n```javascript []\nconst pathSum = (root, targetSum) => {\n    if (root === null) return 0;\n    let count = 0;\n    const st = [root];\n    const path = [];\n    while (st.length !== 0) {\n        const node = st.pop();\n        if (node !== null) {\n            path.push(node.val);\n            st.push(null);\n            if (node.right !== null) st.push(node.right);\n            if (node.left !== null) st.push(node.left);\n            for (let i = path.length - 1, sum = 0; i >= 0; --i) {\n                sum += path[i];\n                if(sum === targetSum) ++count;\n            }\n        } else {\n            path.pop();\n        }\n    }\n    return count;\n};\n```\n# Recursion + Array $$O(n*depth)$$ Beats 81%.\n```javascript []\nconst pathSum = (root, targetSum, path = []) => {\n    if (root === null) return 0;\n    path.push(root.val);\n    let count = 0;\n    for (let i = path.length - 1, sum = 0; i >= 0; --i) {\n        sum += path[i];\n        if (sum === targetSum) ++count;\n    }\n    count += pathSum(root.left, targetSum, path);\n    count += pathSum(root.right, targetSum, path);\n    path.pop();\n    return count;\n};\n```\n# Recursion + Recursion $$O(n*depth)$$ Beats 53%.\n```javascript []\nconst sum = (root, targetSum) => {\n    if (root === null) return 0;\n    let count = 0;\n    targetSum -= root.val;\n    if (targetSum === 0) ++count;\n    count += sum(root.left, targetSum);\n    count += sum(root.right, targetSum);\n    return count;\n}\nconst pathSum = (root, targetSum) => {\n    if (root === null) return 0;\n    let count = 0;\n    count += sum(root, targetSum);\n    count += pathSum(root.left, targetSum);\n    count += pathSum(root.right, targetSum);\n    return count;\n};\n```\n# Stack + Map $$O(n)$$ Beats 96%.\n```javascript []\nconst pathSum = (root, targetSum) => {\n    if (root === null) return 0;\n    let count = 0;\n    const st = [0, root];\n    const m = new Map([[0, 1]]);\n    while (st.length !== 0) {\n        const node = st.pop();\n        if (node !== null) {\n            const sum = st.pop() + node.val;\n            count += m.get(sum - targetSum) ?? 0;\n            m.set(sum, (m.get(sum) ?? 0) + 1);\n            st.push(sum, null);\n            if (node.right !== null) st.push(sum, node.right);\n            if (node.left !== null) st.push(sum, node.left);\n        } else {\n            const sum = st.pop();\n            m.set(sum, m.get(sum) - 1);\n        }\n    }\n    return count;\n};\n```\n# Recursion + Map $$O(n)$$ Beats 98%.\n```javascript []\nconst pathSum = (root, targetSum, sum = 0, m = new Map([[0, 1]])) => {\n    if (root === null) return 0;\n    let count = 0;\n    sum += root.val;\n    count += m.get(sum - targetSum) ?? 0;\n    m.set(sum, (m.get(sum) ?? 0) + 1);\n    count += pathSum(root.left, targetSum, sum, m);\n    count += pathSum(root.right, targetSum, sum, m);\n    m.set(sum, m.get(sum) - 1);\n    return count;\n};\n```
['Stack', 'Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'JavaScript']