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

Commitc0be90a

Browse files
Update
1 parent1a0da92 commitc0be90a

9 files changed

+233
-39
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,8 @@
8787
*[二叉树：前中后序迭代方式的写法就不能统一一下么？](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg)
8888
*[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)
8989
*[二叉树：你真的会翻转二叉树么？](https://mp.weixin.qq.com/s/6gY1MiXrnm-khAAJiIb5Bg)
90+
*[本周小结！（二叉树）](https://mp.weixin.qq.com/s/JWmTeC7aKbBfGx4TY6uwuQ)
91+
*[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)
9092

9193
（持续更新中....）
9294

@@ -282,6 +284,7 @@
282284
|[0515.在每个树行中找最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0515.在每个树行中找最大值.md)|二叉树|简单|**广度优先搜索/队列**|
283285
|[0538.把二叉搜索树转换为累加树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0538.把二叉搜索树转换为累加树.md)|二叉树|简单|**递归****迭代**|
284286
|[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)|字符串|简单|**模拟**|
287+
|[0559.N叉树的最大深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0559.N叉树的最大深度.md)|N叉树|简单|**递归**|
285288
|[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)|哈希表|简单|**哈希**|
286289
|[0589.N叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0589.N叉树的前序遍历.md)|树|简单|**递归****栈/迭代**|
287290
|[0590.N叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0590.N叉树的后序遍历.md)|树|简单|**递归****栈/迭代**|
8.74 KB
Loading

‎pics/559.N叉树的最大深度.png

30 KB
Loading

‎problems/0100.相同的树.md

Lines changed: 37 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ https://leetcode-cn.com/problems/same-tree/
55

66
这道题目和101 基本是一样的
77

8-
##C++代码
8+
##递归
99

1010
```
1111
class Solution {
@@ -23,4 +23,40 @@ public:
2323
}
2424
};
2525
```
26+
27+
##迭代法
28+
29+
```
30+
lass Solution {
31+
public:
32+
33+
bool isSameTree(TreeNode* p, TreeNode* q) {
34+
if (p == NULL && q == NULL) return true;
35+
if (p == NULL || q == NULL) return false;
36+
queue<TreeNode*> que;
37+
que.push(p); //
38+
que.push(q); //
39+
while (!que.empty()) { //
40+
TreeNode* leftNode = que.front(); que.pop();
41+
TreeNode* rightNode = que.front(); que.pop();
42+
if (!leftNode && !rightNode) { //
43+
continue;
44+
}
45+
46+
//
47+
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
48+
return false;
49+
}
50+
que.push(leftNode->left); //
51+
que.push(rightNode->left); //
52+
que.push(leftNode->right); //
53+
que.push(rightNode->right); //
54+
}
55+
return true;
56+
}
57+
58+
59+
};
60+
```
61+
2662
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
Lines changed: 119 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,33 @@
11
##题目地址
22
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
33

4-
##思路
4+
>“简单题”系列
5+
6+
看完本篇可以一起做了如下两道题目：
7+
* 104.二叉树的最大深度
8+
* 559.N叉树的最大深度
9+
10+
#104.二叉树的最大深度
11+
12+
给定一个二叉树，找出其最大深度。
13+
14+
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
15+
16+
说明: 叶子节点是指没有子节点的节点。
17+
18+
示例：
19+
给定二叉树[3,9,20,null,null,15,7]，
20+
21+
<imgsrc='../pics/104. 二叉树的最大深度.png'width=600> </img></div>
22+
23+
返回它的最大深度 3 。
24+
25+
#思路
26+
27+
##递归法
28+
29+
本题其实也要后序遍历（左右中），依然是因为要通过递归函数的返回值做计算树的高度。
530

6-
###递归法
731
按照递归三部曲，来看看如何来写。
832

933
1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
@@ -12,69 +36,71 @@ https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
1236
```
1337
int getDepth(TreeNode* node)
1438
```
39+
1540
2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0。
1641

1742
代码如下：
1843
```
1944
if (node == NULL) return 0;
2045
```
2146

22-
3. 确定单层递归的逻辑：先求它的左子树的深度，再求的右子树的深度，最后去左右深度最大的数值+1 就是目前节点为根节点的树的深度。
47+
3. 确定单层递归的逻辑：先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再+1（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
2348

2449
代码如下：
2550

2651
```
27-
int leftDepth = getDepth(node->left);
28-
int rightDepth = getDepth(node->right);
29-
int depth = 1 + max(leftDepth, rightDepth);
52+
int leftDepth = getDepth(node->left); // 左
53+
int rightDepth = getDepth(node->right); // 右
54+
int depth = 1 + max(leftDepth, rightDepth); // 中
3055
return depth;
3156
```
3257

33-
所以整体代码如下：
58+
所以整体C++代码如下：
3459

3560
```
3661
class Solution {
3762
public:
3863
int getDepth(TreeNode* node) {
3964
if (node == NULL) return 0;
40-
return 1 + max(getDepth(node->left), getDepth(node->right));
65+
int leftDepth = getDepth(node->left); // 左
66+
int rightDepth = getDepth(node->right); // 右
67+
int depth = 1 + max(leftDepth, rightDepth); // 中
68+
return depth;
4169
}
4270
int maxDepth(TreeNode* root) {
4371
return getDepth(root);
4472
}
4573
};
4674
```
4775

48-
###迭代法
76+
代码精简之后C++代码如下：
77+
```
78+
class Solution {
79+
public:
80+
int maxDepth(TreeNode* root) {
81+
if (root == NULL) return 0;
82+
return 1 + max(maxDepth(root->left), maxDepth(root->right));
83+
}
84+
};
4985
50-
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：
86+
```
5187

52-
![层序遍历](https://img-blog.csdnimg.cn/20200810193056585.png)
88+
**精简之后的代码根本看不出是哪种遍历方式，也看不出递归三部曲的步骤，所以如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。**
5389

54-
所以这道题依然是一道模板题，依然可以使用二叉树层序遍历的模板来解决的。
5590

56-
我总结的算法模板会放到这里[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)，大家可以去看一下。
91+
##迭代法
5792

58-
代码如下：
93+
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
5994

60-
##C++代码
95+
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：
6196

62-
###递归
97+
![层序遍历](https://img-blog.csdnimg.cn/20200810193056585.png)
6398

64-
```
65-
class Solution {
66-
public:
67-
int getDepth(TreeNode* node) {
68-
if (node == NULL) return 0;
69-
return 1 + max(getDepth(node->left), getDepth(node->right));
70-
}
71-
int maxDepth(TreeNode* root) {
72-
return getDepth(root);
73-
}
74-
};
75-
```
99+
所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。
100+
101+
如果对层序遍历还不清楚的话，可以看这篇：[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)
76102

77-
###迭代法
103+
C++代码如下：
78104

79105
```
80106
class Solution {
@@ -85,8 +111,8 @@ public:
85111
queue<TreeNode*> que;
86112
que.push(root);
87113
while(!que.empty()) {
88-
int size = que.size(); // 必须要这么写，要固定size大小
89-
depth++;// 记录深度
114+
int size = que.size();
115+
depth++; // 记录深度
90116
for (int i = 0; i < size; i++) {
91117
TreeNode* node = que.front();
92118
que.pop();
@@ -99,4 +125,66 @@ public:
99125
};
100126
```
101127

128+
那么我们可以顺便解决一下N叉树的最大深度问题
129+
130+
#559.N叉树的最大深度
131+
https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
132+
133+
给定一个 N 叉树，找到其最大深度。
134+
135+
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
136+
137+
例如，给定一个 3叉树 :
138+
139+
<imgsrc='../pics/559.N叉树的最大深度.png'width=600> </img></div>
140+
141+
我们应返回其最大深度，3。
142+
143+
#思路
144+
145+
依然可以提供递归法和迭代法，来解决这个问题，思路是和二叉树思路一样的，直接给出代码如下：
146+
147+
##递归法
148+
149+
C++代码：
150+
151+
```
152+
class Solution {
153+
public:
154+
int maxDepth(Node* root) {
155+
if (root == 0) return 0;
156+
int depth = 0;
157+
for (int i = 0; i < root->children.size(); i++) {
158+
depth = max (depth, maxDepth(root->children[i]));
159+
}
160+
return depth + 1;
161+
}
162+
};
163+
```
164+
##迭代法
165+
166+
依然是层序遍历，代码如下：
167+
168+
```
169+
class Solution {
170+
public:
171+
int maxDepth(Node* root) {
172+
queue<Node*> que;
173+
if (root != NULL) que.push(root);
174+
int depth = 0;
175+
while (!que.empty()) {
176+
int size = que.size();
177+
depth++; // 记录深度
178+
for (int i = 0; i < size; i++) {
179+
Node* node = que.front();
180+
que.pop();
181+
for (int i = 0; i < node->children.size(); i++) {
182+
if (node->children[i]) que.push(node->children[i]);
183+
}
184+
}
185+
}
186+
return depth;
187+
}
188+
};
189+
```
102190
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

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

Lines changed: 17 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,14 +4,11 @@ https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
44

55
##思路
66

7-
这道题目建议和[0104.二叉树的最大深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0104.二叉树的最大深度.md)一起来做。
7+
看完了这篇[二叉树：看看这些树的最大深度]()，再来看看如何求最小深度。
88

9-
来来来，一起递归三部曲：
10-
11-
* 确定递归函数的参数和返回值
12-
* 确定终止条件
13-
* 确定单层递归的逻辑
9+
直觉上好像和求最大深度差不多，其实还是差挺多的，一起来看一下。
1410

11+
来来来，一起递归三部曲：
1512

1613
1. 确定递归函数的参数和返回值
1714

@@ -33,8 +30,21 @@ int getDepth(TreeNode* node)
3330
if (node == NULL) return 0;
3431
```
3532

33+
3. 确定单层递归的逻辑
34+
35+
这块和求最大深度可就不一样了，一些同学可能会写如下代码
3636

37-
2. 确定单层递归的逻辑
37+
```
38+
int leftDepth = getDepth(node->left);
39+
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);
47+
```
3848

3949
首先取左右子树的深度，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
4050

‎problems/0144.二叉树的前序遍历.md

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,15 @@ https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
44
#思路
55
这篇文章，**彻底讲清楚应该如何写递归，并给出了前中后序三种不同的迭代法，然后分析迭代法的代码风格为什么没有统一，最后给出统一的前中后序迭代法的代码，帮大家彻底吃透二叉树的深度优先遍历。**
66

7+
对二叉树基础理论还不清楚的话，可以看看这个[关于二叉树，你该了解这些！](https://mp.weixin.qq.com/s/_ymfWYvTNd2GvWvC5HOE4A)。
8+
9+
[二叉树：一入递归深似海，从此offer是路人](https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA)介绍了二叉树的前后中序的递归遍历方式。
10+
11+
[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)介绍了二叉树的前后中序迭代写法。
12+
13+
[二叉树：前中后序迭代方式的写法就不能统一一下么？](https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRg) 介绍了二叉树前中后迭代方式的统一写法。
14+
15+
以下开始开始正文：
716

817
* 二叉树深度优先遍历
918
* 前序遍历：[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)

‎problems/0429.N叉树的层序遍历.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@ https://leetcode-cn.com/problems/sum-of-left-leaves/
88

99
##C++代码
1010

11+
###递归法
12+
1113
```
1214
class Solution {
1315
public:
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
##地址
2+
3+
##思路
4+
5+
##C++代码
6+
7+
###递归法
8+
9+
```
10+
class Solution {
11+
public:
12+
int maxDepth(Node* root) {
13+
if (root == 0) return 0;
14+
int depth = 0;
15+
for (int i = 0; i < root->children.size(); i++) {
16+
depth = max (depth, maxDepth(root->children[i]));
17+
}
18+
return depth + 1;
19+
}
20+
};
21+
```
22+
###迭代法
23+
24+
```
25+
class Solution {
26+
public:
27+
int maxDepth(Node* root) {
28+
queue<Node*> que;
29+
if (root != NULL) que.push(root);
30+
int depth = 0;
31+
while (!que.empty()) {
32+
int size = que.size();
33+
vector<int> vec;
34+
depth++;
35+
for (int i = 0; i < size; i++) {
36+
Node* node = que.front();
37+
que.pop();
38+
for (int i = 0; i < node->children.size(); i++) {
39+
if (node->children[i]) que.push(node->children[i]);
40+
}
41+
}
42+
}
43+
return depth;
44+
}
45+
};
46+
```

0 commit comments

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