python3 DFS + 哈希表，双O(n)复杂度。
利用哈希表维护：从根出发的路径和 及其 对应的条数。
当前节点，如果是这样的情况：当前累加和temp - 目标和sum 在哈希表出现，则意味着出现了累加和sum，累加和sum的条数就是temp - sum的条数。如果没出现temp - sum，也就没出现sum。当前累加和同理，出现了则+1，没出现作为键写入哈希表，值为1。
（temp - sum + sum = temp，总和temp，temp-sum的条数就是sum的条数，想象一张琴的琴弦（两端都固定在一点上的），一端有多条路径和为temp-sum的路，那么自然也有同样多条路径和为sum的路，到达另一端）
理解了这个哈希表的作用，剩下就好理解了。
class Solution: def FindPath(self, root: TreeNode, sum: int) -> int: # 哈希表来记录路径和（从根）及对应条数 # 路径和为0的有1条 self.mp = dict() self.mp[0] = 1 # lastsum为到上一层为止的累加和 def dfs(root: TreeNode, sum: int, lastsum: int) -> int: # 空结点直接返回 if root is None: return 0 res = 0 # 到目前结点为止的累加和 temp = root.val + lastsum # 如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支 if (temp - sum) in self.mp: # 加上有的路径数 res += self.mp[temp - sum] # 增加该次路径和 if temp in self.mp: self.mp[temp] += 1 else: self.mp[temp] = 1 # 进入子结点 res += dfs(root.left, sum, temp) res += dfs(root.right, sum, temp) # 回退该路径和，因为别的树枝不会经过这里了 self.mp[temp] -= 1 return res return dfs(root, sum, 0)
京公网安备 11010502036488号