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

Commit71d8678

Browse files
Update
1 parentdd2d8a0 commit71d8678

7 files changed

+170
-44
lines changed

‎README.md

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -67,7 +67,16 @@
6767
*[字符串：前缀表不右移，难道就写不出KMP了？](https://mp.weixin.qq.com/s/p3hXynQM2RRROK5c6X7xfw)
6868
*[字符串：总结篇！](https://mp.weixin.qq.com/s/gtycjyDtblmytvBRFlCZJg)
6969

70-
*[双指针法：总结篇！](https://mp.weixin.qq.com/s/_p7grwjISfMh0U65uOyCjA)
70+
* 双指针法
71+
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
72+
*[字符串：这道题目，使用库函数一行代码搞定](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
73+
*[字符串：替换空格](https://mp.weixin.qq.com/s/t0A9C44zgM-RysAQV3GZpg)
74+
*[字符串：花式反转还不够！](https://mp.weixin.qq.com/s/X3qpi2v5RSp08mO-W5Vicw)
75+
*[链表：听说过两天反转链表又写不出来了？](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
76+
*[链表：环找到了，那入口呢？](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
77+
*[哈希表：解决了两数之和，那么能解决三数之和么？](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
78+
*[双指针法：一样的道理，能解决四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
79+
*[双指针法：总结篇！](https://mp.weixin.qq.com/s/_p7grwjISfMh0U65uOyCjA)
7180

7281
* 栈与队列
7382
*[栈与队列：来看看栈和队列不为人知的一面](https://mp.weixin.qq.com/s/VZRjOccyE09aE-MgLbCMjQ)

‎problems/0106.从中序与后序遍历序列构造二叉树.md

Lines changed: 113 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,44 @@
11
##题目地址
22
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
33

4+
>给出两个序列
5+
6+
#106.从中序与后序遍历序列构造二叉树
7+
8+
根据一棵树的中序遍历与后序遍历构造二叉树。
9+
10+
注意:
11+
你可以假设树中没有重复的元素。
12+
13+
例如，给出
14+
15+
中序遍历 inorder = [9,3,15,20,7]
16+
后序遍历 postorder =[9,15,7,20,3]
17+
返回如下的二叉树：
18+
19+
<imgsrc='../pics/106. 从中序与后序遍历序列构造二叉树1.png'width=600> </img></div>
20+
421
##思路
522

6-
首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以后序数组最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
23+
首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
724

825
如果让我们肉眼看两个序列，画一颗二叉树的话，应该分分钟都可以画出来。
926

1027
流程如图：
1128

12-
1329
<imgsrc='../pics/106.从中序与后序遍历序列构造二叉树.png'width=600> </img></div>
1430

1531
那么代码应该怎么写呢？
1632

17-
说道一层一层切割，就应该想到了递归。
33+
说到一层一层切割，就应该想到了递归。
1834

1935
来看一下一共分几步：
2036

2137
* 第一步：如果数组大小为零的话，说明是空节点了。
2238

2339
* 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
2440

25-
* 第三步：找到后序数组最后一个元素在后序数组的位置，作为切割点
41+
* 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
2642

2743
* 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
2844

@@ -35,36 +51,38 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
3551
```
3652
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
3753
54+
// 第一步
3855
if (postorder.size() == 0) return NULL;
3956
40-
// 后序遍历数组最后一个元素，就是当前的中间节点
57+
//第二步：后序遍历数组最后一个元素，就是当前的中间节点
4158
int rootValue = postorder[postorder.size() - 1];
4259
TreeNode* root = new TreeNode(rootValue);
4360
4461
// 叶子节点
4562
if (postorder.size() == 1) return root;
4663
47-
找切割点
64+
// 第三步：找切割点
4865
int delimiterIndex;
4966
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
5067
if (inorder[delimiterIndex] == rootValue) break;
5168
}
5269
53-
切割中序数组，得到 中序左数组和中序右数组
54-
切割后序数组，得到 后序左数组和后序右数组
70+
// 第四步：切割中序数组，得到 中序左数组和中序右数组
71+
// 第五步：切割后序数组，得到 后序左数组和后序右数组
5572
73+
// 第六步
5674
root->left = traversal(中序左数组, 后序左数组);
5775
root->right = traversal(中序右数组, 后序右数组);
5876
5977
return root;
6078
}
6179
```
6280

63-
难点大家应该发现了，如何切割呢，边界值找不好很容易乱套。
81+
**难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。**
6482

6583
此时应该注意确定切割的标准，是左闭右开，还有左开又闭，还是左闭又闭，这个就是不变量，要在递归中保持这个不变量。
6684

67-
在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭又闭，必要乱套！
85+
**在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭又闭，必然乱套！**
6886

6987
我在[数组：每次遇到二分法，都是一看就会，一写就废](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)和[数组：这个循环可以转懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)中都强调过循环不变量的重要性，在二分查找以及螺旋矩阵的求解中，坚持循环不变量非常重要，本题也是。
7088

@@ -77,17 +95,16 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
7795

7896

7997
```
80-
// 找到中序遍历的切割点
81-
int delimiterIndex;
82-
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
83-
if (inorder[delimiterIndex] == rootValue) break;
84-
}
85-
86-
// 左闭右开区间
87-
// [0, delimiterIndex)
88-
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
89-
// [delimiterIndex + 1, end)
90-
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
98+
// 找到中序遍历的切割点
99+
int delimiterIndex;
100+
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
101+
if (inorder[delimiterIndex] == rootValue) break;
102+
}
103+
104+
// 左闭右开区间：[0, delimiterIndex)
105+
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
106+
// [delimiterIndex + 1, end)
107+
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
91108
```
92109

93110
接下来就要切割后序数组了。
@@ -96,7 +113,7 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
96113

97114
后序数组的切割点怎么找？
98115

99-
后序数组没有明确的切割元素来进行左右切割，不想中序数组有明确的切割左右，左右分开就可以了。
116+
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
100117

101118
**此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。**
102119

@@ -105,28 +122,27 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
105122
代码如下：
106123

107124
```
108-
// postorder 舍弃末尾元素
109-
postorder.resize(postorder.size() - 1);
125+
// postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
126+
postorder.resize(postorder.size() - 1);
110127
111-
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
112-
// [0, leftInorder.size)
113-
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
114-
// [leftInorder.size(), end)
115-
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
128+
// 左闭右开，注意这里使用了左中序数组大小作为切割点：[0, leftInorder.size)
129+
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
130+
// [leftInorder.size(), end)
131+
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
116132
```
117133

118-
此时，中序数组切成了左中序数组和右中序数组，后序数组切割成序数组和右后序数组。
134+
此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。
119135

120136
接下来可以递归了，代码如下：
121137

122138
```
123-
root->left = traversal(leftInorder, leftPostorder);
124-
root->right = traversal(rightInorder, rightPostorder);
139+
root->left = traversal(leftInorder, leftPostorder);
140+
root->right = traversal(rightInorder, rightPostorder);
125141
```
126142

127143
完整代码如下：
128144

129-
##C++完整代码
145+
###C++完整代码
130146

131147
```
132148
class Solution {
@@ -206,6 +222,7 @@ private:
206222
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
207223
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
208224
225+
// 一下为日志
209226
cout << "----------" << endl;
210227
211228
cout << "leftInorder :";
@@ -244,11 +261,11 @@ public:
244261
};
245262
```
246263

247-
**此时应该发现了，如上的代码性能并不好，应为每层递归定定义了新的vector，既耗时又耗空间，但是上面的代码是最好理解的，为了方便读者理解，所以用如上的代码来讲解。**
264+
**此时应该发现了，如上的代码性能并不好，应为每层递归定定义了新的vector（就是数组），既耗时又耗空间，但上面的代码是最好理解的，为了方便读者理解，所以用如上的代码来讲解。**
248265

249266
下面给出用下表索引写出的代码版本：（思路是一样的，只不过不用重复定义vector了，每次用下表索引来分割）
250267

251-
##C++最终优化版本
268+
###C++优化版本
252269
```
253270
class Solution {
254271
private:
@@ -368,7 +385,24 @@ public:
368385

369386
#105. 从前序与中序遍历序列构造二叉树
370387

371-
同样的道理
388+
根据一棵树的前序遍历与中序遍历构造二叉树。
389+
390+
注意:
391+
你可以假设树中没有重复的元素。
392+
393+
例如，给出
394+
395+
前序遍历 preorder = [3,9,20,15,7]
396+
中序遍历 inorder =[9,3,15,20,7]
397+
返回如下的二叉树：
398+
399+
<imgsrc='../pics/105. 从前序与中序遍历序列构造二叉树.png'width=600> </img></div>
400+
401+
##思路
402+
403+
本题和106是一样的道理。
404+
405+
我就直接给出代码了。
372406

373407
带日志的版本C++代码如下： （**带日志的版本仅用于调试，不要在leetcode上提交，会超时**）
374408

@@ -444,9 +478,8 @@ public:
444478
};
445479
```
446480

447-
105.从前序与中序遍历序列构造二叉树，最后版本：
481+
105.从前序与中序遍历序列构造二叉树，最后版本，C++代码：
448482

449-
C++代码：
450483
```
451484
class Solution {
452485
private:
@@ -493,3 +526,45 @@ public:
493526
}
494527
};
495528
```
529+
530+
#思考题
531+
532+
前序和中序可以唯一确定一颗二叉树。
533+
534+
后序和中序可以唯一确定一颗二叉树。
535+
536+
那么前序和后序可不可以唯一确定一颗二叉树呢？
537+
538+
**前序和后序不能唯一确定一颗二叉树！**，因为没有中序遍历无法确定左右部分，也就是无法分割。
539+
540+
举一个例子：
541+
542+
<imgsrc='../pics/106.从中序与后序遍历序列构造二叉树2.png'width=600> </img></div>
543+
544+
tree1 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。
545+
546+
tree2 的前序遍历是[1 2 3]， 后序遍历是[3 2 1]。
547+
548+
那么tree1 和 tree2 的前序和后序完全相同，这是一棵树么，很明显是两棵树！
549+
550+
所以前序和后序不能唯一确定一颗二叉树！
551+
552+
#总结
553+
554+
之前我们讲的二叉树题目都是各种遍历二叉树，这次开始构造二叉树了，思路其实比较简单，但是真正代码实现出来并不容易。
555+
556+
所以要避免眼高手低，踏实的把代码写出来。
557+
558+
我同时给出了添加日志的代码版本，因为这种题目是不太容易写出来调一调就能过的，所以一定要把流程日志打出来，看看符不符合自己的思路。
559+
560+
大家遇到这种题目的时候，也要学会打日志来调试（如何打日志有时候也是个技术活），不要脑动模拟，脑动模拟很容易越想越乱。
561+
562+
最后我还给出了为什么前序和中序可以唯一确定一颗二叉树，后序和中序可以唯一确定一颗二叉树，而前序和后序却不行。
563+
564+
认真研究完本篇，相信大家对二叉树的构造会清晰很多。
565+
566+
如果学到了，就赶紧转发给身边需要的同学吧！
567+
568+
加个油！
569+
570+

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

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -165,20 +165,17 @@ public:
165165
queue<TreeNode*> que;
166166
que.push(root);
167167
while(!que.empty()) {
168-
int size = que.size();
168+
int size = que.size();
169169
depth++; // 记录最小深度
170-
int flag = 0;
171170
for (int i = 0; i < size; i++) {
172171
TreeNode* node = que.front();
173172
que.pop();
174173
if (node->left) que.push(node->left);
175174
if (node->right) que.push(node->right);
176175
if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
177-
flag = 1;
178-
break;
176+
return depth;
179177
}
180178
}
181-
if (flag == 1) break;
182179
}
183180
return depth;
184181
}

‎problems/0141.环形链表.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2+
##思路
3+
4+
可以使用快慢指针法， 分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
5+
6+
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢？
7+
8+
首先第一点：**fast指针一定先进入环中，如果fast 指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。**
9+
10+
那么来看一下，**为什么fast指针和slow指针一定会相遇呢？**
11+
12+
可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。
13+
14+
会发现最终都是这种情况， 如下图：
15+
16+
<imgsrc='../pics/142环形链表1.png'width=600> </img></div>
17+
18+
fast和slow各自再走一步， fast和slow就相遇了
19+
20+
这是因为fast是走两步，slow是走一步，**其实相对于slow来说，fast是一个节点一个节点的靠近slow的**，所以fast一定可以和slow重合。
21+
22+
23+
##C++代码如下
24+
25+
```
26+
class Solution {
27+
public:
28+
bool hasCycle(ListNode *head) {
29+
ListNode* fast = head;
30+
ListNode* slow = head;
31+
while(fast != NULL && fast->next != NULL) {
32+
slow = slow->next;
33+
fast = fast->next->next;
34+
// 快慢指针相遇，说明有环
35+
if (slow == fast) return true;
36+
}
37+
return false;
38+
}
39+
};
40+
```
41+
##扩展
42+
43+
做完这道题目，可以在做做142.环形链表II，不仅仅要找环，还要找环的入口。
44+
45+
142.环形链表II题解：[链表：环找到了，那入口呢？](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)

0 commit comments

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