0113. 路径总和 II · ttttt

# 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))，这里的所有的解法使用通用方法解答。除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。我们先来看下通用解法的解题思路，我画了一张图： ![](https://img.kancloud.cn/46/ec/46ec3382e572355e2109c47284e37e4b_1341x1080.jpg) > 图是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)，都差不多，仅做参考。通用写法的具体代码见下方代码区。 ## 关键点解析 - 回溯法 - backtrack 解题公式 ## 代码 - 语言支持：JS，C++，Python3 JavaScript Code： ``` <pre class="calibre18">``` /* * @lc app=leetcode id=113 lang=javascript * * [113] Path Sum II */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ function backtrack(root, sum, res, tempList) { if (root === null) return; if (root.left === null && root.right === null && sum === root.val) return 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(); } /** * @param {TreeNode} root * @param {number} sum * @return {number[][]} */ var pathSum = function(root, sum) { if (root === null) return []; const res = []; backtrack(root, sum, res, []); return res; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int sum) { auto ret = vector<vector<int>>(); auto temp = vector<int>(); backtrack(root, sum, ret, temp); return ret; } private: void backtrack(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& tempList) { if (root == nullptr) return; tempList.push_back(root->val); if (root->val == sum && root->left == nullptr && root->right == nullptr) { ret.push_back(tempList); } else { backtrack(root->left, sum - root->val, ret, tempList); backtrack(root->right, sum - root->val, ret, tempList); } tempList.pop_back(); } }; ``` ``` ``` <pre class="calibre18">``` # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]: if not root: return [] result = [] def trace_node(pre_list, left_sum, node): new_list = pre_list.copy() new_list.append(node.val) if not node.left and not node.right: # 这个判断可以和上面的合并，但分开写会快几毫秒，可以省去一些不必要的判断 if left_sum == node.val: result.append(new_list) else: if node.left: trace_node(new_list, left_sum-node.val, node.left) if node.right: trace_node(new_list, left_sum-node.val, node.right) trace_node([], sum, root) return 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)