12-line Python O(N) guaranteed
Just copy the code from another problem Maximum size subarray sum which is solved by an O(N) algorithm.\n\n\nclass Solution(object):\n    def pathSum(self, root
Just copy the code from another problem Maximum size subarray sum which is solved by an O(N) algorithm.\n\n```\nclass Solution(object):\n    def pathSum(self, root, target):\n        """\n        :type root: TreeNode\n        :type target: int\n        :rtype: int\n        """\n        self.count = 0\n        preDict = {0: 1}\n        def dfs(p, target, pathSum, preDict):\n            if p:\n                pathSum += p.val\n                self.count += preDict.get(pathSum - target, 0)\n                preDict[pathSum] = preDict.get(pathSum, 0) + 1\n                dfs(p.left, target, pathSum, preDict)\n                dfs(p.right, target, pathSum, preDict)\n                preDict[pathSum] -= 1\n        dfs(root, target, 0, preDict)\n        return self.count\n```
[]