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)