[Python] dfs + hash table, using cumulative sums, explained
If we can have any solution, that this problem is indeed medium. However if we wan to have O(n) time solution, in my opinion it is more like hard, because we ne
If we can have any solution, that this problem is indeed medium. However if we wan to have `O(n)` time solution, in my opinion it is more like hard, because we need to use dfs + hash table in the same time.\n\nFirst of all, let us evaluate cumulative sum of our tree, what does it mean? Here an example: for each node we evaluate sum of path from this node to root.\n\n![image](https://assets.leetcode.com/users/images/119b5a72-5244-4cd7-bb6e-60784d94c2a0_1596872120.09719.png)\n\n\nAlso we evaluate number of nodes in our tree. What we need to find now? Number of pairs of two nodes, one of them is descendant of another and difference of cumulative sums is equal to `sum`. Let me explain my `dfs(self, root, sum)` function:\n\n1. If we reached `None`, just go back.\n2. We have `self.count` hash table, where we put `root.val + sum`: number we are looking for when we visited this node: for example if we are in node with value `15` now (see our example), then we want to find node with values `15+8` inside. \n3. Also, we add to our final result number of solution for our `root.val`. \n4. Run recursively our `dfs` for left and right children\n5. Remove our `root.val + sum` from our hash table, because we are not anymore in `root` node.\n\nNow, let us consider our `pathSum(self, root, sum)` function:\n1. If tree is empty, we return `0`\n2. Define some global variables.\n3. Run our `cumSum` function to evaluate cumulative sums\n4. Run `dfs` method.\n5. In the end we need to subtract `self.n*(sum == 0)` from our result. Why? Because if `sum = 0`, then we will count exactly `self.n` empty cumulative sums, which consist of zero elements.\n\n**Complexity**: Time complexity to evaluate cumulative sums is `O(n)`. The same time complexity is for `dfs` function. Space complexity is also `O(n)`, because we need to keep this amount of information in our `count` hash table.\n\n```\nclass Solution:\n    def cumSum(self, root):\n        self.n += 1\n        for child in filter(None, [root.left, root.right]):\n            child.val += root.val\n            self.cumSum(child)\n                \n    def dfs(self, root, sum):\n        if not root: return None\n        \n        self.count[root.val + sum] += 1\n        self.result += self.count[root.val]\n        self.dfs(root.left, sum)\n        self.dfs(root.right, sum)\n        self.count[root.val + sum] -= 1\n \n    def pathSum(self, root, sum):\n        if not root: return 0\n        \n        self.n, self.result, self.count = 0, 0, defaultdict(int)\n        self.cumSum(root)\n        self.count[sum] = 1\n        self.dfs(root, sum)\n        return self.result  - self.n*(sum == 0) \n```\n\n**Update**: thanks @rkmd for pointing out that we do not really need to evaluate cumlative sums, we can do in on the fly. Also if we do it on the fly, we do not need to check case if `sum == 0`. Here is the code:\n\n```\nclass Solution:\n    def dfs(self, root, sum, root_sum):\n        if not root: return None\n        \n        root_sum += root.val\n        self.result += self.count[root_sum]  \n        self.count[root_sum + sum] += 1\n        self.dfs(root.left, sum, root_sum)\n        self.dfs(root.right, sum, root_sum)\n        self.count[root_sum + sum] -= 1\n \n    def pathSum(self, root, sum):\n        self.result, self.count = 0, defaultdict(int)\n        self.count[sum] = 1\n        self.dfs(root, sum, 0)\n        return self.result\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']