LeetCode 437 路径和 III

给定一个二叉树，它的每个节点都包含一个整数值。

找到路径总数并等于给定值。

路径不需要从根节点开始，也不需要在叶节点结束，但路径方向必须向下（只能从父节点到子节点）。

二叉树不超过 1000 个节点，节点取值范围为 [-1000000,1000000] 的整数。

示例：root = [10,5，-3,3,2，null，11,3，-2，null，1]， sum = 8

hashmap 阿里腾讯字节问题是求解从任意节点到后代节点的路径，并将其求和为指定值。 请注意，它不必从根节点开始或在叶节点结束。

一个简单的思维方式是直接递归求解，空间复杂度为o（n），时间复杂度介于o（nlogn）和o（n 2）之间，具体**：

/** definition for a binary tree node. *function treenode(val) /// the number of the paths starting from selffunction helper(root, sum) /** param root * param sum * return */var pathsum = function (root, sum) ;

这里有一个区别，我将解释为什么会有一个hashmap[acc] = hashmap[acc] -1;原因很简单，就是当我们 dfs 的时候，当我们从底部回到顶部时，地图的值也应该回溯。 如果你熟悉回顾法，应该很容易理解，这个问题就通过了templist.pop()完成。

另外，我画了一张图，相信你看完就会明白了。

当我们到达底部时：

然后返回：

很容易看出，我们的哈希图不应该与第一个哈希图具有相同的记录，因此需要减去它。

有关具体实现，请参阅下面的 ** 区域。

通过hashmap，空间换时间语言支持：js、pythonjs代码：

lc app=leetcode id=437 lang=j**ascript * 437] path sum iii *//** definition for a binary tree node. *function treenode(val) /function helper(root, acc, target, hashmap) if (hashmap[acc] === void 0) else const res = count + helper(root.left, acc, target, hashmap) +helper(root.right, acc, target, hashmap);请注意，这里不要忘记 hashmap[acc] = hashmap[acc] -1; return res;}var pathsum = function (root, sum) ;return helper(root, 0, sum, hashmap);}python code:

import collections'''class treenode: def __init__(self, val=0, left=none, right=none): self.val = val self.left = left self.right = right'''class solution: def helper(self,root,acc,target,hashmap): if not root: return 0 count=0 acc+=root.val if acc==target: count+=1 if acc-target in hashmap: count+=hashmap[acc-target] hashmap[acc]+=1 if root.left: count+=self.helper(root.left,acc,target,hashmap) if root.right: count+=self.helper(root.right,acc,target,hashmap) hashmap[acc]-=1 return count def pathsum(self, root: optional[treenode], targetsum: int) -int: hashmap=collections.defaultdict(lambda:0) return self.helper(root,0,targetsum,hashmap)