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

Commit865f054

Browse files
Update
1 parentc0be90a commit865f054

9 files changed

+134
-41
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@
8989
*[二叉树：你真的会翻转二叉树么？](https://mp.weixin.qq.com/s/6gY1MiXrnm-khAAJiIb5Bg)
9090
*[本周小结！（二叉树）](https://mp.weixin.qq.com/s/JWmTeC7aKbBfGx4TY6uwuQ)
9191
*[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)
92+
*[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)
9293

9394
（持续更新中....）
9495

@@ -317,6 +318,7 @@
317318

318319
#我的公众号
319320

321+
320322
更多精彩文章持续更新，微信搜索：「代码随想录」第一时间围观，关注后回复： 「简历模板」「java」「C++」「python」「算法与数据结构」 等关键字就可以获得我多年整理出来的学习资料。
321323

322324
**每天8：35准时为你推送一篇经典面试题目，帮你梳理算法知识体系，轻松学习算法！**，并且公众号里有大量学习资源，也有我自己的学习心得和方法总结，相信你一定会有所收获！

‎pics/111.二叉树的最小深度.png

82.7 KB
Loading
8.99 KB
Loading

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

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -250,23 +250,27 @@ public:
250250
##C++代码
251251

252252
```
253+
class Solution {
254+
public:
255+
vector<int> largestValues(TreeNode* root) {
253256
queue<TreeNode*> que;
254257
if (root != NULL) que.push(root);
255-
vector<vector<int>> result;
258+
vector<int> result;
256259
while (!que.empty()) {
257260
int size = que.size();
258-
vector<int> vec;
259-
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
261+
int maxValue = INT_MIN; // 取每一层的最大值
260262
for (int i = 0; i < size; i++) {
261263
TreeNode* node = que.front();
262264
que.pop();
263-
vec.push_back(node->val);
265+
maxValue =node->val > maxValue ? node->val : maxValue;
264266
if (node->left) que.push(node->left);
265267
if (node->right) que.push(node->right);
266268
}
267-
result.push_back(vec);
269+
result.push_back(maxValue); // 把最大值放进数组
268270
}
269271
return result;
272+
}
273+
};
270274
```
271275

272276
#116.填充每个节点的下一个右侧节点指针

‎problems/0104.二叉树的最大深度.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -187,4 +187,38 @@ public:
187187
}
188188
};
189189
```
190+
191+
使用栈来模拟后序遍历依然可以
192+
193+
```
194+
class Solution {
195+
public:
196+
int maxDepth(TreeNode* root) {
197+
stack<TreeNode*> st;
198+
if (root != NULL) st.push(root);
199+
int depth = 0;
200+
int result = 0;
201+
while (!st.empty()) {
202+
TreeNode* node = st.top();
203+
if (node != NULL) {
204+
st.pop();
205+
st.push(node); // 中
206+
st.push(NULL);
207+
depth++;
208+
if (node->right) st.push(node->right); // 右
209+
if (node->left) st.push(node->left); // 左
210+
211+
} else {
212+
st.pop();
213+
node = st.top();
214+
st.pop();
215+
depth--;
216+
}
217+
result = result > depth ? result : depth;
218+
}
219+
return result;
220+
221+
}
222+
};
223+
```
190224
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0111.二叉树的最小深度.md

Lines changed: 87 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,39 @@
22
##题目地址
33
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
44

5-
##思路
5+
>和求最大深度一个套路？
66
7-
看完了这篇[二叉树：看看这些树的最大深度]()，再来看看如何求最小深度。
7+
#111.二叉树的最小深度
88

9-
直觉上好像和求最大深度差不多，其实还是差挺多的，一起来看一下。
9+
给定一个二叉树，找出其最小深度。
10+
11+
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
12+
13+
说明: 叶子节点是指没有子节点的节点。
14+
15+
示例:
16+
17+
给定二叉树 [3,9,20,null,null,15,7],
18+
19+
<imgsrc='../pics/111.二叉树的最小深度1.png'width=600> </img></div>
20+
21+
返回它的最小深度 2.
22+
23+
#思路
24+
25+
看完了这篇[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)，再来看看如何求最小深度。
26+
27+
直觉上好像和求最大深度差不多，其实还是差不少的。
28+
29+
遍历顺序上依然是后序遍历（因为要比较递归返回之后的结果），但在处理中间节点的逻辑上，最大深度很容易理解，最小深度可有一个误区，如图：
30+
31+
<imgsrc='../pics/111.二叉树的最小深度.png'width=600> </img></div>
32+
33+
这就重新审题了，题目中说的是：**最小深度是从根节点到最近叶子节点的最短路径上的节点数量。**，注意是**叶子节点**。
34+
35+
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
36+
37+
##递归法
1038

1139
来来来，一起递归三部曲：
1240

@@ -32,59 +60,63 @@ if (node == NULL) return 0;
3260

3361
3. 确定单层递归的逻辑
3462

35-
这块和求最大深度可就不一样了，一些同学可能会写如下代码
36-
63+
这块和求最大深度可就不一样了，一些同学可能会写如下代码：
3764
```
3865
int leftDepth = getDepth(node->left);
3966
int rightDepth = getDepth(node->right);
40-
if (node->left == NULL && node->right != NULL) { 
41-
    return 1 + rightDepth;
42-
}   
43-
if (node->left != NULL && node->right == NULL) { 
44-
    return 1 + leftDepth;
45-
}
46-
return 1 + min(leftDepth, rightDepth);
67+
int result = 1 + min(leftDepth, rightDepth);
68+
return result;
4769
```
4870

49-
首先取左右子树的深度，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
71+
这个代码就犯了此图中的误区：
72+
73+
<imgsrc='../pics/111.二叉树的最小深度.png'width=600> </img></div>
5074

51-
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 就可以了。
75+
如果这么求的话，没有左孩子的分支会算为最短深度。
5276

53-
可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
77+
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
78+
79+
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
5480

5581
代码如下：
5682

5783
```
58-
int leftDepth = getDepth(node->left);
59-
int rightDepth = getDepth(node->right);
84+
int leftDepth = getDepth(node->left); // 左
85+
int rightDepth = getDepth(node->right); // 右
86+
// 中
87+
// 当一个左子树为空，右不为空，这时并不是最低点
6088
if (node->left == NULL && node->right != NULL) { 
6189
    return 1 + rightDepth;
6290
}   
91+
// 当一个右子树为空，左不为空，这时并不是最低点
6392
if (node->left != NULL && node->right == NULL) { 
6493
    return 1 + leftDepth;
6594
}
66-
return 1 + min(leftDepth, rightDepth);
95+
int result = 1 + min(leftDepth, rightDepth);
96+
return result;
6797
```
6898

69-
整体递归代码如下：
70-
71-
##C++代码
99+
遍历的顺序为后序（左右中），可以看出：**求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。**
72100

73-
###递归
101+
整体递归代码如下：
74102
```
75103
class Solution {
76104
public:
77105
int getDepth(TreeNode* node) {
78106
if (node == NULL) return 0;
107+
int leftDepth = getDepth(node->left); // 左
108+
int rightDepth = getDepth(node->right); // 右
109+
// 中
79110
// 当一个左子树为空，右不为空，这时并不是最低点
80-
if(node->left ==NULL &&node->right !=NULL) {
81-
return 1 + getDepth(node->right);
82-
}
111+
if (node->left == NULL && node->right != NULL) { 
112+
    return 1 + rightDepth;
113+
}   
83114
// 当一个右子树为空，左不为空，这时并不是最低点
84-
if(node->left !=NULL &&node->right ==NULL) {
85-
return 1 + getDepth(node->left);
115+
if (node->left != NULL && node->right == NULL) { 
116+
    return 1 + leftDepth;
86117
}
87-
return 1 + min(getDepth(node->left), getDepth(node->right));
118+
int result = 1 + min(leftDepth, rightDepth);
119+
return result;
88120
}
89121
90122
int minDepth(TreeNode* root) {
@@ -93,15 +125,36 @@ public:
93125
};
94126
```
95127

96-
###迭代法
128+
精简之后代码如下：
97129

98-
可以使用二叉树的广度优先遍历（层序遍历），来做这道题目，其实这就是一道模板题了，二叉树的层序遍历模板在这道题解中[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)
130+
```
131+
class Solution {
132+
public:
133+
int minDepth(TreeNode* root) {
134+
if (root == NULL) return 0;
135+
if (root->left == NULL && root->right != NULL) {
136+
return 1 + minDepth(root->right);
137+
}
138+
if (root->left != NULL && root->right == NULL) {
139+
return 1 + minDepth(root->left);
140+
}
141+
return 1 + min(minDepth(root->left), minDepth(root->right));
142+
}
143+
};
144+
```
145+
146+
**精简之后的代码根本看不出是哪种遍历方式，所以依然还要强调一波：如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。**
147+
148+
##迭代法
99149

100-
层序遍历如图所示：
150+
相对于[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)，本题还可以使用层序遍历的方式来解决，思路是一样的。
101151

102-
![最小深度](https://img-blog.csdnimg.cn/20200811194719677.png)
152+
如果对层序遍历还不清楚的话，可以看这篇：[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)
153+
154+
**需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点**
103155

104156
代码如下：（详细注释）
157+
105158
```
106159
class Solution {
107160
public:
@@ -112,8 +165,8 @@ public:
112165
queue<TreeNode*> que;
113166
que.push(root);
114167
while(!que.empty()) {
115-
int size = que.size();// 必须要这么写，要固定size大小
116-
depth++;
168+
int size = que.size();
169+
depth++; // 记录最小深度
117170
int flag = 0;
118171
for (int i = 0; i < size; i++) {
119172
TreeNode* node = que.front();

‎problems/0222.完全二叉树的节点个数.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ public:
4040
for (int i = 0; i < size; i++) {
4141
TreeNode* node = que.front();
4242
que.pop();
43-
result++; //记录遍历的层数
43+
result++; //记录节点数量
4444
if (node->left) que.push(node->left);
4545
if (node->right) que.push(node->right);
4646
}

‎problems/0701.二叉搜索树中的插入操作.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
1111

1212
例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，**需要调整二叉树的结构么？ 并不需要。**只需要遍历二叉搜索树，找到空节点 插入元素就可以了， 那么这道题其实就非常简单了。
1313

14-
<videosrc='../video/701.二叉搜索树中的插入操作.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
14+
<imgsrc='../video/701.二叉搜索树中的插入操作.gif'width=600> </img></div>
1515

1616
接下来就是遍历二叉搜索树的过程了。
1717

Loading

0 commit comments

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