# 0113. 路徑總和 II ## 題目地址(113. 路徑總和 II) <https://leetcode-cn.com/problems/path-sum-ii/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等于給定目標和的路徑。 說明: 葉子節點是指沒有子節點的節點。 示例: 給定如下二叉樹，以及目標和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] ``` ``` ## 前置知識 - 回溯法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目是求集合，并不是`求值`，而是枚舉所有可能，因此動態規劃不是特別切合，因此我們需要考慮別的方法。 這種題目其實有一個通用的解法，就是回溯法。 網上也有大神給出了這種回溯法解題的 [通用寫法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning))，這里的所有的解法使用通用方法解答。 除了這道題目還有很多其他題目可以用這種通用解法，具體的題目見后方相關題目部分。 我們先來看下通用解法的解題思路，我畫了一張圖：  > 圖是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，僅做參考。 通用寫法的具體代碼見下方代碼區。 ## 關鍵點解析 - 回溯法 - backtrack 解題公式 ## 代碼 - 語言支持：JS，C++，Python3 JavaScript Code： ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=113 lang=javascript * * [113] Path Sum II */</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">backtrack</span>(<span class="hljs-params">root, sum, res, tempList</span>) </span>{ <span class="hljs-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span>; <span class="hljs-keyword">if</span> (root.left === <span class="hljs-params">null</span> && root.right === <span class="hljs-params">null</span> && sum === root.val) <span class="hljs-keyword">return</span> res.push([...tempList, root.val]); tempList.push(root.val); backtrack(root.left, sum - root.val, res, tempList); backtrack(root.right, sum - root.val, res, tempList); tempList.pop(); } <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-keyword">if</span> (root === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> []; <span class="hljs-keyword">const</span> res = []; backtrack(root, sum, res, []); <span class="hljs-keyword">return</span> res; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>> pathSum(TreeNode* root, <span class="hljs-keyword">int</span> sum) { <span class="hljs-keyword">auto</span> ret = <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>>(); <span class="hljs-keyword">auto</span> temp = <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>(); backtrack(root, sum, ret, temp); <span class="hljs-keyword">return</span> ret; } <span class="hljs-keyword">private</span>: <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">backtrack</span><span class="hljs-params">(<span class="hljs-keyword">const</span> TreeNode* root, <span class="hljs-keyword">int</span> sum, <span class="hljs-params">vector</span><<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>>& ret, <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& tempList)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span>; tempList.push_back(root->val); <span class="hljs-keyword">if</span> (root->val == sum && root->left == <span class="hljs-params">nullptr</span> && root->right == <span class="hljs-params">nullptr</span>) { ret.push_back(tempList); } <span class="hljs-keyword">else</span> { backtrack(root->left, sum - root->val, ret, tempList); backtrack(root->right, sum - root->val, ret, tempList); } tempList.pop_back(); } }; ``` ``` ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for a binary tree node.</span> <span class="hljs-title"># class TreeNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.left = None</span> <span class="hljs-title"># self.right = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pathSum</span><span class="hljs-params">(self, root: TreeNode, sum: int)</span> -> List[List[int]]:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> [] result = [] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trace_node</span><span class="hljs-params">(pre_list, left_sum, node)</span>:</span> new_list = pre_list.copy() new_list.append(node.val) <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> node.left <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> node.right: <span class="hljs-title"># 這個判斷可以和上面的合并，但分開寫會快幾毫秒，可以省去一些不必要的判斷</span> <span class="hljs-keyword">if</span> left_sum == node.val: result.append(new_list) <span class="hljs-keyword">else</span>: <span class="hljs-keyword">if</span> node.left: trace_node(new_list, left_sum-node.val, node.left) <span class="hljs-keyword">if</span> node.right: trace_node(new_list, left_sum-node.val, node.right) trace_node([], sum, root) <span class="hljs-keyword">return</span> result ``` ``` ## 相關題目 - [39.combination-sum](39.combination-sum.html) - [40.combination-sum-ii](40.combination-sum-ii.html) - [46.permutations](46.permutations.html) - [47.permutations-ii](47.permutations-ii.html) - [78.subsets](78.subsets.html) - [90.subsets-ii](90.subsets-ii.html) - [131.palindrome-partitioning](131.palindrome-partitioning.html)