第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0113. 路径总和 II
题目地址(113. 路径总和 II)
题目描述
1
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
2
3
说明: 叶子节点是指没有子节点的节点。
4
5
示例:
6
给定如下二叉树，以及目标和 sum = 22，
7
8
5
9
/ \
10
4 8
11
/ / \
12
11 13 4
13
/ \ / \
14
7 2 5 1
15
返回:
16
17
[
18
[5,4,11,2],
19
[5,8,4,5]
20
]
Copied!
前置知识
- 回溯法
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这道题目是求集合，并不是
求值，而是枚举所有可能，因此动态规划不是特别切合，因此我们需要考虑别的方法。这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning))，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路，我画了一张图：
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- backtrack 解题公式
代码
- 语言支持：JS，C++，Python3
JavaScript Code：
1
/*
2
* @lc app=leetcode id=113 lang=javascript
3
*
4
* [113] Path Sum II
5
*/
6
/**
7
* Definition for a binary tree node.
8
* function TreeNode(val) {
9
* this.val = val;
10
* this.left = this.right = null;
11
* }
12
*/
13
function backtrack(root, sum, res, tempList) {
14
if (root === null) return;
15
if (root.left === null && root.right === null && sum === root.val)
16
return res.push([...tempList, root.val]);
17
18
tempList.push(root.val);
19
backtrack(root.left, sum - root.val, res, tempList);
20
21
backtrack(root.right, sum - root.val, res, tempList);
22
tempList.pop();
23
}
24
/**
25
* @param {TreeNode} root
26
* @param {number} sum
27
* @return {number[][]}
28
*/
29
var pathSum = function (root, sum) {
30
if (root === null) return [];
31
const res = [];
32
backtrack(root, sum, res, []);
33
return res;
34
};
Copied!
C++ Code:
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
vector<vector<int>> pathSum(TreeNode* root, int sum) {
13
auto ret = vector<vector<int>>();
14
auto temp = vector<int>();
15
backtrack(root, sum, ret, temp);
16
return ret;
17
}
18
private:
19
void backtrack(const TreeNode* root, int sum, vector<vector<int>>& ret, vector<int>& tempList) {
20
if (root == nullptr) return;
21
tempList.push_back(root->val);
22
if (root->val == sum && root->left == nullptr && root->right == nullptr) {
23
ret.push_back(tempList);
24
} else {
25
backtrack(root->left, sum - root->val, ret, tempList);
26
backtrack(root->right, sum - root->val, ret, tempList);
27
}
28
tempList.pop_back();
29
}
30
};
Copied!
1
# Definition for a binary tree node.
2
# class TreeNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.left = None
6
# self.right = None
7
8
class Solution:
9
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
10
if not root:
11
return []
12
13
result = []
14
15
def trace_node(pre_list, left_sum, node):
16
new_list = pre_list.copy()
17
new_list.append(node.val)
18
if not node.left and not node.right:
19
# 这个判断可以和上面的合并，但分开写会快几毫秒，可以省去一些不必要的判断
20
if left_sum == node.val:
21
result.append(new_list)
22
else:
23
if node.left:
24
trace_node(new_list, left_sum-node.val, node.left)
25
if node.right:
26
trace_node(new_list, left_sum-node.val, node.right)
27
28
trace_node([], sum, root)
29
return result
Copied!
相关题目
最近更新 1yr ago