# 0437. 路徑總和 III ## 題目地址(437. 路徑總和 III) <https://leetcode-cn.com/problems/path-sum-iii/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹，它的每個結點都存放著一個整數值。 找出路徑和等于給定數值的路徑總數。 路徑不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點）。 二叉樹不超過1000個節點，且節點數值范圍是 [-1000000,1000000] 的整數。 示例： root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 返回 3。和等于 8 的路徑有: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 ``` ``` ## 前置知識 - hashmap ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目是要我們求解出任何一個節點出發到子孫節點的路徑中和為指定值。 注意這里，不一定是從根節點出發，也不一定在葉子節點結束。 一種簡單的思路就是直接遞歸解決，空間復雜度O(n) 時間復雜度介于O(nlogn) 和 O(n^2)， 具體代碼： ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">// the number of the paths starting from self</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">root, sum</span>) </span>{ <span class="hljs-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> l = helper(root.left, sum - root.val); <span class="hljs-keyword">const</span> r = helper(root.right, sum - root.val); <span class="hljs-keyword">return</span> l + r + (root.val === sum ? <span class="hljs-params">1</span> : <span class="hljs-params">0</span>); } <span class="hljs-title">/** * @param {TreeNode} root * @param {number} sum * @return {number} */</span> <span class="hljs-keyword">var</span> pathSum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root, sum</span>) </span>{ <span class="hljs-title">// 空間復雜度O(n) 時間復雜度介于O(nlogn) 和 O(n^2)</span> <span class="hljs-title">// tag: dfs tree</span> <span class="hljs-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-title">// the number of the paths starting from self</span> <span class="hljs-keyword">const</span> self = helper(root, sum); <span class="hljs-title">// we don't know the answer, so we just pass it down</span> <span class="hljs-keyword">const</span> l = pathSum(root.left, sum); <span class="hljs-title">// we don't know the answer, so we just pass it down</span> <span class="hljs-keyword">const</span> r = pathSum(root.right, sum); <span class="hljs-keyword">return</span> self + l + r; }; ``` ``` 但是還有一種空間復雜度更加優秀的算法，利用hashmap來避免重復計算，時間復雜度和空間復雜度都是O(n)。 這種思路是`subarray-sum-equals-k`的升級版本，如果那道題目你可以O(n)解決，這道題目難度就不會很大， 只是將數組換成了二叉樹。關于具體的思路可以看[這道題目](560.subarray-sum-equals-k.html) 這里有一個不一樣的地方，這里我說明一下，就是為什么要有`hashmap[acc] = hashmap[acc] - 1;`， 原因很簡單，就是我們DFS的時候，從底部往上回溯的時候，map的值應該也回溯。如果你對回溯法比較熟悉的話， 應該很容易理解，如果不熟悉可以參考[這道題目](46.permutations.html)， 這道題目就是通過`tempList.pop()`來完成的。 另外我畫了一個圖，相信看完你就明白了。 當我們執行到底部的時候：  接著往上回溯：  很容易看出，我們的hashmap不應該有第一張圖的那個記錄了，因此需要減去。 具體實現見下方代碼區。 ## 關鍵點解析 - 通過hashmap，以時間換空間 - 對于這種連續的元素求和問題，有一個共同的思路，可以參考[這道題目](560.subarray-sum-equals-k.html) ## 代碼 - 語言支持：JS ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=437 lang=javascript * * [437] Path Sum III */</span> <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">helper</span>(<span class="hljs-params">root, acc, target, hashmap</span>) </span>{ <span class="hljs-title">// see also : https://leetcode.com/problems/subarray-sum-equals-k/</span> <span class="hljs-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; acc += root.val; <span class="hljs-keyword">if</span> (acc === target) count++; <span class="hljs-keyword">if</span> (hashmap[acc - target] !== <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { count += hashmap[acc - target]; } <span class="hljs-keyword">if</span> (hashmap[acc] === <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { hashmap[acc] = <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { hashmap[acc] += <span class="hljs-params">1</span>; } <span class="hljs-keyword">const</span> res = count + helper(root.left, acc, target, hashmap) + helper(root.right, acc, target, hashmap); <span class="hljs-title">// 這里要注意別忘記了</span> hashmap[acc] = hashmap[acc] - <span class="hljs-params">1</span>; <span class="hljs-keyword">return</span> res; } <span class="hljs-keyword">var</span> pathSum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root, sum</span>) </span>{ <span class="hljs-keyword">const</span> hashmap = {}; <span class="hljs-keyword">return</span> helper(root, <span class="hljs-params">0</span>, sum, hashmap); }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。