Easy O(N) solution | hashmap | C++ Code Commented
\nclass Solution {\npublic:\n    unordered_map<long, int> map;\n    int count = 0;\n    \n    void countPathSum(TreeNode* root, int target, long sum){\n        
```\nclass Solution {\npublic:\n    unordered_map<long, int> map;\n    int count = 0;\n    \n    void countPathSum(TreeNode* root, int target, long sum){\n        if(!root)\n            return;\n        sum += root->val;        //Path sum from root\n        if(sum == target)\n            count++;\n        if(map.find(sum - target) != map.end())         //checking whether any target sum path present in the path from root to the current node\n            count += map[sum - target];\n        map[sum]++;\n        countPathSum(root->left, target, sum);\n        countPathSum(root->right, target, sum);\n        map[sum]--;      //After visiting the left and right subtree, we have to reduce this path sum count from map since we are leaving this path\n    }\n    \n    int pathSum(TreeNode* root, int targetSum) {\n        countPathSum(root, targetSum, 0);\n        return count;\n    }\n};\n```\n\n* **Time Complexity = O(N)**, where N is the no of nodes in the binary tree. In the recursion we are visiting each node only once. Hence O(N) T.C.\n* **Space Complexity = O(N)**, Our hashmap takes O(N) space, also we need to concider the space taken by the recursive function calls, in the worst case of a skew binary tree, our stack can contain upto N function calls.\n**IF YOU FIND IT HELPFUL, SHOW SOME LOVE IN THE FORM OF UPVOTE\uD83D\uDE0D**
['C', 'Binary Tree']