Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdd2d8a0

Browse files
Update
1 parent61f88b3 commitdd2d8a0

8 files changed

+185
-47
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,7 @@
9797
*[还在玩耍的你，该总结啦！（本周小结之二叉树）](https://mp.weixin.qq.com/s/QMBUTYnoaNfsVHlUADEzKg)
9898
*[二叉树：以为使用了递归，其实还隐藏着回溯](https://mp.weixin.qq.com/s/ivLkHzWdhjQQD1rQWe6zWA)
9999
*[二叉树：做了这么多题目了，我的左叶子之和是多少？](https://mp.weixin.qq.com/s/gBAgmmFielojU5Wx3wqFTA)
100+
*[二叉树：我的左下角的值是多少？](https://mp.weixin.qq.com/s/MH2gbLvzQ91jHPKqiub0Nw)
100101

101102

102103

‎pics/112.路径总和.png

4 KB
Loading

‎pics/112.路径总和1.png

13.2 KB
Loading

‎pics/113.路径总和II1.png

25.7 KB
Loading

‎problems/0112.路径总和.md

Lines changed: 180 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,81 +1,114 @@
11
##题目地址
22

3+
>递归函数什么时候需要返回值
4+
35
#112. 路径总和
46

5-
##思路
7+
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
68

7-
相信大家看到千篇一律的写法：
8-
```
9-
class Solution {
10-
public:
11-
bool hasPathSum(TreeNode* root, int sum) {
12-
if (root == NULL) return false;
13-
if (!root->left && !root->right && sum == root->val) {
14-
return true;
15-
}
16-
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
17-
}
18-
};
19-
```
20-
**这种写法简短是简短，但其实对于读者理解不是很友好，没有很好的体现出递归的顺序已经背后的回溯。**
9+
说明: 叶子节点是指没有子节点的节点。
10+
11+
示例: 
12+
给定如下二叉树，以及目标和 sum = 22，
2113

22-
**相信很多同学都疑惑递归的过程中究竟什么时候需要返回值，什么时候不需要返回值？**
14+
<imgsrc='../pics/112.路径总和1.png'width=600> </img></div>
15+
16+
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
17+
18+
#思路
19+
20+
这道题我们要遍历从根节点到叶子节点的的路径看看总和是不是目标和。
21+
22+
##递归
23+
24+
可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树
25+
26+
1. 确定递归函数的参数和返回类型
27+
28+
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
29+
30+
**再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？**
31+
32+
在文章[二叉树：我的左下角的值是多少？](https://mp.weixin.qq.com/s/MH2gbLvzQ91jHPKqiub0Nw)中，我给出了一个结论：
2333

2434
**如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。**
2535

26-
而本题就要要搜索一条路径，使其上所有节点值相加等于目标和，所以递归需要返回值！
36+
在[二叉树：我的左下角的值是多少？](https://mp.weixin.qq.com/s/MH2gbLvzQ91jHPKqiub0Nw)中，因为要遍历树的所有路径，找出深度最深的叶子节点，所以递归函数不要返回值。
37+
38+
而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？
2739

2840
如图所示：
2941

3042
<imgsrc='../pics/112.路径总和.png'width=600> </img></div>
3143

3244
图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。
3345

34-
那么使用深度优先遍历的方式（本题前中后序都可以，无所谓）来遍历二叉树，如下代码我尽量将每一步清晰的表现出来，C++代码如下：
46+
所以代码如下：
3547

3648
```
37-
class Solution {
38-
private:
39-
bool traversal(TreeNode* cur, int count) {
40-
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
41-
42-
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回
49+
bool traversal(TreeNode* cur, int count) // 注意函数的返回类型
50+
```
4351

44-
if (cur->left) { // 左 （空节点不遍历）
45-
// 遇到叶子节点返回true，则直接返回true
46-
if (traversal(cur->left, count - cur->left->val)) return true;
47-
}
48-
if (cur->right) { // 右 （空节点不遍历）
49-
// 遇到叶子节点返回true，则直接返回true
50-
if (traversal(cur->right, count - cur->right->val)) return true;
51-
}
52-
return false;
53-
}
5452

55-
public:
56-
bool hasPathSum(TreeNode* root, int sum) {
57-
if (root == NULL) return false;
58-
return traversal(root, sum - root->val);
59-
}
60-
};
53+
2. 确定终止条件
54+
55+
首先计数器如何统计这一条路径的和呢？
56+
57+
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
58+
59+
如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
60+
61+
如果遍历到了叶子节点，count不为0，就是没找到。
62+
63+
递归终止条件代码如下：
64+
65+
```
66+
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
67+
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回
6168
```
6269

70+
3. 确定单层递归的逻辑
71+
72+
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
73+
74+
递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。
75+
76+
代码如下：
77+
78+
```
79+
if (cur->left) { // 左 （空节点不遍历）
80+
// 遇到叶子节点返回true，则直接返回true
81+
if (traversal(cur->left, count - cur->left->val)) return true; // 注意这里有回溯的逻辑
82+
}
83+
if (cur->right) { // 右 （空节点不遍历）
84+
// 遇到叶子节点返回true，则直接返回true
85+
if (traversal(cur->right, count - cur->right->val)) return true; // 注意这里有回溯的逻辑
86+
}
87+
return false;
88+
```
6389

64-
那么其实本题一定是有回溯的，没有回溯，如何后撤重新找另一条路径呢，但是貌似以上代码中，**大家貌似没有感受到回溯，那是因为回溯在代码里隐藏起来了。**
90+
以上代码中是包含着回溯的，没有回溯，如何后撤重新找另一条路径呢。
6591

66-
隐藏在`traversal(cur->left, count - cur->left->val)`这里， 因为把`count - cur->left->val` 直接作为参数传进去，函数结束，count自然恢复到原先的数值了。
92+
回溯隐藏在`traversal(cur->left, count - cur->left->val)`这里， 因为把`count - cur->left->val` 直接作为参数传进去，函数结束，count的数值没有改变。
6793

68-
为了把回溯的过程体现出来，将`if (traversal(cur->left, count - cur->left->val)) return true;` 改为如下代码：
94+
为了把回溯的过程体现出来，可以改为如下代码：
6995

7096
```
7197
if (cur->left) { // 左
7298
count -= cur->left->val; // 递归，处理节点;
7399
if (traversal(cur->left, count)) return true;
74100
count += cur->left->val; // 回溯，撤销处理结果
75101
}
102+
if (cur->right) { // 右
103+
count -= cur->right->val;
104+
if (traversal(cur->right, count - cur->right->val)) return true;
105+
count += cur->right->val;
106+
}
107+
return false;
76108
```
77109

78-
这样大家就能感受到回溯了，整体回溯代码如下：
110+
111+
整体代码如下：
79112

80113
```
81114
class Solution {
@@ -105,9 +138,29 @@ public:
105138
};
106139
```
107140

141+
以上代码精简之后如下：
142+
143+
```
144+
class Solution {
145+
public:
146+
bool hasPathSum(TreeNode* root, int sum) {
147+
if (root == NULL) return false;
148+
if (!root->left && !root->right && sum == root->val) {
149+
return true;
150+
}
151+
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
152+
}
153+
};
154+
```
155+
156+
**是不是发现精简之后的代码，已经完全看不出分析的过程了，所以我们要把题目分析清楚之后，在追求代码精简。** 这一点我已经强调很多次了！
157+
158+
159+
##迭代
160+
108161
如果使用栈模拟递归的话，那么如果做回溯呢？
109162

110-
此时栈里一个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。
163+
**此时栈里一个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。**
111164

112165
C++就我们用pair结构来存放这个栈里的元素。
113166

@@ -146,3 +199,85 @@ public:
146199
}
147200
};
148201
```
202+
203+
如果大家完全理解了本地的递归方法之后，就可以顺便把leetcode上113. 路径总和II做了。
204+
205+
#113. 路径总和II
206+
207+
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
208+
209+
说明: 叶子节点是指没有子节点的节点。
210+
211+
示例:
212+
给定如下二叉树，以及目标和 sum = 22，
213+
214+
215+
<imgsrc='../pics/113.路径总和II1.png'width=600> </img></div>
216+
217+
##思路
218+
219+
113.路径总和II要遍历整个树，找到所有路径，**所以递归函数不要返回值！**
220+
221+
如图：
222+
223+
<imgsrc='../pics/113.路径总和II.png'width=600> </img></div>
224+
225+
226+
为了尽可能的把细节体现出来，我写出如下代码（**这份代码并不简洁，但是逻辑非常清晰**）
227+
228+
```
229+
class Solution {
230+
private:
231+
vector<vector<int>> result;
232+
vector<int> path;
233+
// 递归函数不需要返回值，因为我们要遍历整个树
234+
void traversal(TreeNode* cur, int count) {
235+
if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点切找到了和为sum的路径
236+
result.push_back(path);
237+
return;
238+
}
239+
240+
if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回
241+
242+
if (cur->left) { // 左 （空节点不遍历）
243+
path.push_back(cur->left->val);
244+
count -= cur->left->val;
245+
traversal(cur->left, count); // 递归
246+
count += cur->left->val; // 回溯
247+
path.pop_back(); // 回溯
248+
}
249+
if (cur->right) { // 右 （空节点不遍历）
250+
path.push_back(cur->right->val);
251+
count -= cur->right->val;
252+
traversal(cur->right, count); // 递归
253+
count += cur->right->val; // 回溯
254+
path.pop_back(); // 回溯
255+
}
256+
return ;
257+
}
258+
259+
public:
260+
vector<vector<int>> pathSum(TreeNode* root, int sum) {
261+
result.clear();
262+
path.clear();
263+
if (root == NULL) return result;
264+
path.push_back(root->val); // 把根节点放进路径
265+
traversal(root, sum - root->val);
266+
return result;
267+
}
268+
};
269+
```
270+
271+
至于113. 路径总和II 的迭代法我并没有写，用迭代方式记录所有路径比较麻烦，也没有必要，如果大家感兴趣的话，可以再深入研究研究。
272+
273+
#总结
274+
275+
本篇通过leetcode上112. 路径总和 和 113. 路径总和II 详细的讲解了 递归函数什么时候需要返回值，什么不需要返回值。
276+
277+
这两道题目是掌握这一知识点非常好的题目，大家看完本篇文章再去做题，就会感受到搜索整棵树和搜索某一路径的差别。
278+
279+
对于112. 路径总和，我依然给出了递归法和迭代法，这种题目其实用迭代法会复杂一些，能掌握递归方式就够了！
280+
281+
今天是长假最后一天了，内容多一些，也是为了尽快让大家恢复学习状态，哈哈。
282+
283+
加个油！

‎problems/0113.路径总和II.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818

1919
如图：
2020

21-
<imgsrc='../pics/107.二叉树的层次遍历II.png'width=600> </img></div>
21+
<imgsrc='../pics/113.路径总和II.png'width=600> </img></div>
2222

2323

2424
这道题目其实比[112. 路径总和](https://leetcode-cn.com/problems/path-sum/)简单一些，大家做完了本题，可以在做[112. 路径总和](https://leetcode-cn.com/problems/path-sum/)。

‎problems/0131.分割回文串.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -135,7 +135,7 @@ private:
135135
} else { // 如果不是则直接跳过
136136
continue;
137137
}
138-
backtracking(s, i + 1, path); // 寻找i+1为起始位置的子串
138+
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
139139
path.pop_back(); // 回溯过程，弹出本次已经填在的子串
140140
}
141141
}

‎problems/0257.二叉树的所有路径.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -207,6 +207,8 @@ public:
207207

208208
那么在如上代码中，**貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在`traversal(cur->left, path + "->", result);`中的`path + "->"`。** 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。
209209

210+
**如果这里还不理解的话，可以看这篇[二叉树：以为使用了递归，其实还隐藏着回溯](https://mp.weixin.qq.com/s/ivLkHzWdhjQQD1rQWe6zWA)，我这这篇中详细的解释了递归中如何隐藏着回溯。**
211+
210212

211213

212214
**综合以上，第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里，第一种递归写法虽然代码多一些，但是把每一个逻辑处理都完整的展现了出来了。**

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp