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

Commit5fc065c

Browse files
Update
1 parent8f5b6cf commit5fc065c

12 files changed

+383
-62
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,7 @@
8585
*[二叉树：一入递归深似海，从此offer是路人](https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA)
8686
*[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)
8787
*[二叉树：前中后序迭代方式的写法就不能统一一下么？](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)
88+
*[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)
8889

8990
（持续更新中....）
9091

@@ -272,6 +273,8 @@
272273
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)|字符创|简单|**KMP**|
273274
|[0486.预测赢家](https://github.com/youngyangyang04/leetcode/blob/master/problems/0486.预测赢家.md)|动态规划|中等|**递归****记忆递归****动态规划**|
274275
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯算法**|
276+
|[0501.二叉搜索树中的众数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0501.二叉搜索树中的众数.md)|二叉树|简单|**递归/中序遍历**|
277+
|[0515.在每个树行中找最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0515.在每个树行中找最大值.md)|二叉树|简单|**广度优先搜索/队列**|
275278
|[0538.把二叉搜索树转换为累加树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0538.把二叉搜索树转换为累加树.md)|二叉树|简单|**递归****迭代**|
276279
|[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)|字符串|简单|**模拟**|
277280
|[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)|哈希表|简单|**哈希**|

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

141 KB
Loading

‎pics/226.翻转二叉树.png

24.4 KB
Loading

‎pics/226.翻转二叉树1.png

88.7 KB
Loading
15.3 KB
Loading

‎problems/0102.二叉树的层序遍历.md

Lines changed: 36 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
33

44
>我要打十个！
55
6-
看完这篇文章虽然不能打十个，但是可以迅速打五个！而且够快！
6+
看完这篇文章虽然不能打十个，但是可以迅速打六个！而且够快！
77

88

99
#102.二叉树的层序遍历
@@ -35,7 +35,7 @@ https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
3535

3636
这样就实现了层序从左到右遍历二叉树。
3737

38-
代码如下：**这份代码也可以作为二叉树层序遍历的模板，以后在打四个就靠它了**。
38+
代码如下：**这份代码也可以作为二叉树层序遍历的模板，以后再打五个就靠它了**。
3939

4040
##C++代码
4141

@@ -64,7 +64,7 @@ public:
6464
};
6565
```
6666

67-
**此时我们就掌握了二叉树的层序遍历了，那么如下四道leetcode上的题目，只需要修改模板的一两行代码（不能再多了），便可打倒！**
67+
**此时我们就掌握了二叉树的层序遍历了，那么如下五道leetcode上的题目，只需要修改模板的一两行代码（不能再多了），便可打倒！**
6868

6969
#107.二叉树的层次遍历 II
7070

@@ -226,6 +226,37 @@ public:
226226
};
227227
```
228228

229+
#515.在每个树行中找最大值
230+
231+
您需要在二叉树的每一行中找到最大的值。
232+
233+
<imgsrc='../pics/515.在每个树行中找最大值.png'width=600> </img></div>
234+
235+
##思路
236+
237+
层序遍历，取每一层的最大值
238+
239+
##C++代码
240+
241+
```
242+
queue<TreeNode*> que;
243+
if (root != NULL) que.push(root);
244+
vector<vector<int>> result;
245+
while (!que.empty()) {
246+
int size = que.size();
247+
vector<int> vec;
248+
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
249+
for (int i = 0; i < size; i++) {
250+
TreeNode* node = que.front();
251+
que.pop();
252+
vec.push_back(node->val);
253+
if (node->left) que.push(node->left);
254+
if (node->right) que.push(node->right);
255+
}
256+
result.push_back(vec);
257+
}
258+
return result;
259+
```
229260
#总结
230261

231262
二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现（此时是不是又发现队列的应用了）。
@@ -237,8 +268,9 @@ public:
237268
* 199.二叉树的右视图
238269
* 637.二叉树的层平均值
239270
* 589.N叉树的前序遍历
271+
* 515.在每个树行中找最大值
240272

241-
虽然不能一口气打十个，打五个也还行。
273+
虽然不能一口气打十个，打六个也还行。
242274

243275
如果非要打十个，还得找叶师傅！
244276

‎problems/0112.路径总和.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
##题目地址
22

3+
#112. 路径总和
4+
35
##思路
46

57
相信大家看到千篇一律的写法：

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

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
2+
##链接
3+
4+
##思路
5+
6+
这道题目与其说是递归，不如说是回溯问题，题目要找到所有的路径。
7+
8+
这道题目相对于[112. 路径总和](https://leetcode-cn.com/problems/path-sum/) ，是要求出所有的路径和。
9+
10+
11+
**相信很多同学都疑惑递归的过程中究竟什么时候需要返回值，什么时候不需要返回值?**
12+
13+
我在[112. 路径总和题解](https://leetcode-cn.com/problems/path-sum/solution/112-lu-jing-zong-he-di-gui-hui-su-die-dai-xiang-ji/)中给出了详细的解释。
14+
15+
**如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。**
16+
17+
而本题要遍历整个树，找到所有路径，**所以本题的递归函数不要返回值！**
18+
19+
如图：
20+
21+
<imgsrc='../pics/107.二叉树的层次遍历II.png'width=600> </img></div>
22+
23+
24+
这道题目其实比[112. 路径总和](https://leetcode-cn.com/problems/path-sum/)简单一些，大家做完了本题，可以在做[112. 路径总和](https://leetcode-cn.com/problems/path-sum/)。
25+
26+
为了尽可能的把回溯过程体现出来，我写出如下代码（**这个代码一定不是最简洁的，但是比较清晰的，过于简洁的代码不方便读者理解**）
27+
28+
29+
##C++代码
30+
31+
```
32+
class Solution {
33+
private:
34+
vector<vector<int>> result;
35+
vector<int> path;
36+
// 递归函数不需要返回值，因为我们要遍历整个树
37+
void traversal(TreeNode* cur, int count) {
38+
if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点切找到了和为sum的路径
39+
result.push_back(path);
40+
return;
41+
}
42+
43+
if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回
44+
45+
if (cur->left) { // 左 （空节点不遍历）
46+
path.push_back(cur->left->val);
47+
count -= cur->left->val;
48+
traversal(cur->left, count); // 递归
49+
count += cur->left->val; // 回溯
50+
path.pop_back(); // 回溯
51+
}
52+
if (cur->right) { // 右 （空节点不遍历）
53+
path.push_back(cur->right->val);
54+
count -= cur->right->val;
55+
traversal(cur->right, count); // 递归
56+
count += cur->right->val; // 回溯
57+
path.pop_back(); // 回溯
58+
}
59+
return ;
60+
}
61+
62+
public:
63+
vector<vector<int>> pathSum(TreeNode* root, int sum) {
64+
result.clear();
65+
path.clear();
66+
if (root == NULL) return result;
67+
path.push_back(root->val); // 把根节点放进路径
68+
traversal(root, sum - root->val);
69+
return result;
70+
}
71+
};
72+
```

‎problems/0226.翻转二叉树.md

Lines changed: 105 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,59 @@
11
##题目地址
22
https://leetcode-cn.com/problems/invert-binary-tree/
33

4-
##思路
4+
#226.翻转二叉树
55

6-
###递归法
7-
写递归算法的时候，要想一想是采用前中后序哪种遍历方式
8-
o
9-
如果对递归还不熟，可以看这里[彻底吃透二叉树的前中后序递归法和迭代法！！](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/che-di-chi-tou-er-cha-shu-de-qian-zhong-hou-xu-d-2/)
6+
翻转一棵二叉树。
107

11-
我们先看看递归算法，对于二叉树的递归方式有三种前中后序，先来看看前序遍历。
8+
<imgsrc='../pics/226.翻转二叉树.png'width=600> </img></div>
129

13-
通过动画来看一下翻转的过程:
10+
这道题目背后有一个让程序员心酸的故事，听说 Homebrew的作者Max Howell，就是因为没在白板上写出翻转二叉树，最后被Google拒绝了。（真假不做判断，权当一个乐子哈）
1411

15-
<videosrc='../video/翻转二叉树.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
12+
#题外话
1613

17-
递归三部曲：
14+
这道题目是非常经典的题目，也是比较简单的题目（至少一看就会）。
15+
16+
但正是因为这道题太简单，一看就会，一些同学都没有抓住起本质，稀里糊涂的就把这道题目过了。
17+
18+
如果做过这道题的同学也建议认真看完，相信一定有所收获！
19+
20+
#思路
21+
22+
我们之前介绍的都是各种方式遍历二叉树，这次要翻转了，感觉还是有点懵逼。
23+
24+
这得怎么翻转呢？
25+
26+
如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：
27+
28+
<imgsrc='../pics/226.翻转二叉树1.png'width=600> </img></div>
29+
30+
可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
31+
32+
关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）
33+
34+
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
35+
36+
**注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果**
37+
38+
**这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不行，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了**
39+
40+
那么层序遍历可以不可以呢？**依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！**
41+
42+
##递归法
43+
44+
对于二叉树的递归法的前中后序遍历，已经在[二叉树：前中后序递归遍历](https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA)详细讲解了。
45+
46+
我们下文以前序遍历为例，通过动画来看一下翻转的过程:
47+
48+
<imgsrc='../video/翻转二叉树.gif'width=600> </img></div>
49+
50+
我们来看一下递归三部曲：
1851

1952
1. 确定递归函数的参数和返回值
2053

21-
参数就是要传入节点的指针，不需要其他参数了，返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就返回一个指针。
54+
参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。
55+
56+
返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为`TreeNode*`。
2257

2358
```
2459
TreeNode* invertTree(TreeNode* root)
@@ -34,7 +69,7 @@ if (root == NULL) return root;
3469

3570
3. 确定单层递归的逻辑
3671

37-
因为是先序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
72+
因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。
3873

3974
```
4075
swap(root->left, root->right);
@@ -49,34 +84,21 @@ class Solution {
4984
public:
5085
TreeNode* invertTree(TreeNode* root) {
5186
if (root == NULL) return root;
52-
swap(root->left, root->right);
53-
invertTree(root->left);
54-
invertTree(root->right);
87+
swap(root->left, root->right); // 中
88+
invertTree(root->left); // 左
89+
invertTree(root->right); // 右
5590
return root;
5691
}
5792
};
5893
```
5994

60-
###迭代法
95+
##迭代法
6196

62-
[leetcode-master](https://github.com/youngyangyang04/leetcode-master) 中给出了 前中后序迭代法统一的模板，使用前序遍历，只需要改动一行就可以了，代码在下面已经给出。
97+
###深度优先遍历
6398

64-
##C++代码
99+
[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)中给出了前中后序迭代方式的写法，所以本地可以很轻松的切出如下迭代法的代码：
65100

66-
###递归（前序遍历）
67-
```
68-
class Solution {
69-
public:
70-
TreeNode* invertTree(TreeNode* root) {
71-
if (root == NULL) return root;
72-
swap(root->left, root->right);
73-
invertTree(root->left);
74-
invertTree(root->right);
75-
return root;
76-
}
77-
};
78-
```
79-
###迭代法（前序遍历）
101+
C++代码迭代法（前序遍历）
80102

81103
```
82104
class Solution {
@@ -86,20 +108,22 @@ public:
86108
stack<TreeNode*> st;
87109
st.push(root);
88110
while(!st.empty()) {
89-
TreeNode* node = st.top();
111+
TreeNode* node = st.top(); // 中
90112
st.pop();
91-
swap(node->left, node->right);
92-
if(node->left) st.push(node->left);
93-
if(node->right) st.push(node->right);
113+
swap(node->left, node->right);
114+
if(node->right) st.push(node->right); // 右
115+
if(node->left) st.push(node->left); // 左
94116
}
95117
return root;
96118
}
97119
};
98120
```
121+
如果这个代码看不懂的话可以在回顾一下[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)。
122+
99123

100-
###迭代法（前序遍历）（模板）
124+
我们在[二叉树：前中后序迭代方式的统一写法](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)中介绍了统一的写法，所以，本题也只需将文中的代码少做修改便可。
101125

102-
模板地址：[leetcode-master](https://github.com/youngyangyang04/leetcode-master)
126+
C++代码如下迭代法（前序遍历）
103127

104128
```
105129
class Solution {
@@ -111,9 +135,9 @@ public:
111135
TreeNode* node = st.top();
112136
if (node != NULL) {
113137
st.pop();
114-
if (node->right) st.push(node->right); //添加右节点
115-
if (node->left) st.push(node->left); //添加左节点
116-
st.push(node); //添加中节点
138+
if (node->right) st.push(node->right); //右
139+
if (node->left) st.push(node->left); //左
140+
st.push(node); //中
117141
st.push(NULL);
118142
} else {
119143
st.pop();
@@ -126,4 +150,45 @@ public:
126150
}
127151
};
128152
```
153+
154+
如果上面这个代码看不懂，回顾一下文章[二叉树：前中后序迭代方式的统一写法](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)。
155+
156+
###广度优先遍历
157+
158+
也就是层序遍历，层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍，代码如下：
159+
160+
```
161+
class Solution {
162+
public:
163+
TreeNode* invertTree(TreeNode* root) {
164+
queue<TreeNode*> que;
165+
if (root != NULL) que.push(root);
166+
while (!que.empty()) {
167+
int size = que.size();
168+
for (int i = 0; i < size; i++) {
169+
TreeNode* node = que.front();
170+
que.pop();
171+
swap(node->left, node->right); // 节点处理
172+
if (node->left) que.push(node->left);
173+
if (node->right) que.push(node->right);
174+
}
175+
}
176+
return root;
177+
}
178+
};
179+
```
180+
如果对以上代码不理解，或者不清楚二叉树的层序遍历，可以看这篇[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)
181+
182+
#总结
183+
184+
针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历。
185+
186+
**二叉树解题的大忌就是自己稀里糊涂的过了（因为这道题相对简单），但是也不知道自己是怎么遍历的。**
187+
188+
这也是造成了二叉树的题目“一看就会，一写就废”的原因。
189+
190+
**针对翻转二叉树，我给出了一种递归，三种迭代（两种模拟深度优先遍历，一种层序遍历）的写法，都是之前我们讲过的写法，融汇贯通一下而已。**
191+
192+
大家一定也有自己的解法，但一定要成方法论，这样才能通用，才能举一反三！
193+
129194
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
2+
##题目地址
3+
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
4+
##思路
5+
详见：
6+
*[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)

0 commit comments

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