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

Commit4aea708

Browse files
Update
1 parent46c6c7c commit4aea708

11 files changed

+219
-9
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -79,6 +79,7 @@
7979
*[栈与队列：滑动窗口里求最大值引出一个重要数据结构](https://mp.weixin.qq.com/s/8c6l2bO74xyMjph09gQtpA)
8080
*[栈与队列：求前 K 个高频元素和队列有啥关系？](https://mp.weixin.qq.com/s/8hMwxoE_BQRbzCc7CA8rng)
8181
*[栈与队列：总结篇！](https://mp.weixin.qq.com/s/xBcHyvHlWq4P13fzxEtkPg)
82+
8283
* 二叉树
8384
*[关于二叉树，你该了解这些！](https://mp.weixin.qq.com/s/_ymfWYvTNd2GvWvC5HOE4A)
8485

‎problems/0028.实现strStr().md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,11 @@ https://leetcode-cn.com/problems/implement-strstr/
2727

2828
本题是KMP 经典题目。
2929

30+
以下文字如果看不进去，可以看我的B站视频：
31+
32+
*[帮你把KMP算法学个通透！B站（理论篇）](https://www.bilibili.com/video/BV1PD4y1o7nd/)
33+
*[帮你把KMP算法学个通透！（求next数组代码篇）](https://www.bilibili.com/video/BV1M5411j7Xx)
34+
3035
KMP的经典思想就是:**当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。**
3136

3237
本篇将以如下顺序来讲解KMP，

‎problems/0112.路径总和.md

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
##题目地址
2+
3+
##思路
4+
// 遍历单条边，还是遍历整个树，取最优数值！！
5+
// 对啊，用sum来减法啊，免得多定义一个变量
6+
7+
##C++
8+
9+
贼粗糙的写法
10+
11+
深度优先遍历
12+
13+
```
14+
class Solution {
15+
private:
16+
bool traversal(TreeNode* cur, int count) {
17+
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
18+
if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
19+
20+
if (cur->left) { // 左
21+
// 遇到叶子节点返回true，则直接返回true
22+
if (traversal(cur->left, count - cur->left->val)) return true;
23+
}
24+
if (cur->right) { // 右
25+
// 遇到叶子节点返回true，则直接返回true
26+
if (traversal(cur->right, count - cur->right->val)) return true;
27+
}
28+
return false;
29+
}
30+
31+
public:
32+
bool hasPathSum(TreeNode* root, int sum) {
33+
if (root == NULL) return false;
34+
return traversal(root, sum - root->val);
35+
}
36+
};
37+
```
38+
39+
其实本题一定是有回溯的，没有回溯，如果后撤重新找另一条路径呢，但是貌似以上代码中，**大家貌似没有感受到回溯，那是因为回溯在代码里隐藏起来了。**
40+
41+
隐藏在`traversal(cur->left, count - cur->left->val)`这里， 因为把`count - cur->left->val` 直接作为参数传进去，函数结束，count自然恢复到原先的数值了。
42+
43+
为了把回溯的过程体现出来，将`if (traversal(cur->left, count - cur->left->val)) return true;` 改为如下代码：
44+
45+
```
46+
if (cur->left) { // 左
47+
count -= cur->left->val; // 递归，处理节点;
48+
if (traversal(cur->left, count)) return true;
49+
count += cur->left->val; // 回溯，撤销处理结果
50+
}
51+
```
52+
53+
这样大家就能感受到回溯了，整体回溯代码如下：
54+
55+
```
56+
class Solution {
57+
private:
58+
bool traversal(TreeNode* cur, int count) {
59+
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
60+
if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
61+
62+
if (cur->left) { // 左
63+
count -= cur->left->val; // 递归，处理节点;
64+
if (traversal(cur->left, count)) return true;
65+
count += cur->left->val; // 回溯，撤销处理结果
66+
}
67+
if (cur->right) { // 右
68+
count -= cur->right->val; // 递归，处理节点;
69+
if (traversal(cur->right, count)) return true;
70+
count += cur->right->val; // 回溯，撤销处理结果
71+
}
72+
return false;
73+
}
74+
75+
public:
76+
bool hasPathSum(TreeNode* root, int sum) {
77+
if (root == NULL) return false;
78+
return traversal(root, sum - root->val);
79+
}
80+
};
81+
```

‎problems/0459.重复的子字符串.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,12 @@ https://leetcode-cn.com/problems/repeated-substring-pattern/
2626

2727
这又是一道标准的KMP的题目。
2828

29+
如果KMP还不够了解，可以看我的B站：
30+
31+
*[帮你把KMP算法学个通透！B站（理论篇）](https://www.bilibili.com/video/BV1PD4y1o7nd/)
32+
*[帮你把KMP算法学个通透！（求next数组代码篇）](https://www.bilibili.com/video/BV1M5411j7Xx)
33+
34+
2935
如果KMP还不够了解，可以看我的这个视频[帮你把KMP算法学个通透！B站](https://www.bilibili.com/video/BV1PD4y1o7nd/)
3036

3137
我们在[字符串：都来看看KMP的看家本领！](https://mp.weixin.qq.com/s/Gk9FKZ9_FSWLEkdGrkecyg)里提到了，在一个串中查找是否出现过另一个串，这是KMP的看家本领。

‎problems/0617.合并二叉树.md

Lines changed: 119 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,121 @@ https://leetcode-cn.com/problems/merge-two-binary-trees/
33

44
##思路
55

6-
四种写法，总有一款适合你，其实这道题目迭代法实现是比较困难的，大家可以试一试，是一道不错的面试进阶题目。
6+
相信这道题目很多同学疑惑的点是如何同时遍历两个二叉树呢？
7+
8+
其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。
9+
10+
那么前中后序应该使用哪种遍历呢？
11+
12+
**本题使用哪种遍历都是可以的！**
13+
14+
我们下面以前序遍历为例。
15+
16+
动画如下：
17+
18+
19+
<imgsrc='../video/617.合并二叉树.gif'width=600> </img></div>
20+
21+
那么我们来按照递归三部曲来解决：
22+
23+
1.**确定递归函数的参数和返回值：**
24+
首先那么要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
25+
26+
代码如下：
27+
28+
```
29+
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
30+
```
31+
32+
2.**确定终止条件：**
33+
34+
因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓）。
35+
36+
反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓）。
37+
38+
代码如下：
39+
40+
```
41+
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
42+
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
43+
```
44+
45+
46+
3.**确定单层递归的逻辑：**
47+
48+
单层递归的逻辑就比较好些了，这里我们用重复利用一下t1这个树，t1就是合并之后树的根节点（所谓的修改了元数据的结构）。
49+
50+
那么单层递归中，就要把两棵树的元素加到一起。
51+
```
52+
t1->val += t2->val;
53+
```
54+
55+
那么此时t1 的左子树 应该是 合并 t1左子树 t2左子树之后的左子树，t1 的右子树 应该是 合并 t1右子树 t2右子树之后的右子树。
56+
57+
代码如下：
58+
59+
```
60+
t1->left = mergeTrees(t1->left, t2->left);
61+
t1->right = mergeTrees(t1->right, t2->right);
62+
return t1;
63+
```
64+
65+
此时前序遍历，修改原输入树结构的完整代码就写出来了，如下：
66+
67+
```
68+
class Solution {
69+
public:
70+
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
71+
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
72+
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
73+
// 修改了t1的数值和结构
74+
t1->val += t2->val; // 中
75+
t1->left = mergeTrees(t1->left, t2->left); // 左
76+
t1->right = mergeTrees(t1->right, t2->right); // 右
77+
return t1;
78+
}
79+
};
80+
```
81+
82+
那么中序遍历可不可以呢，也是可以的，代码如下：
83+
84+
```
85+
class Solution {
86+
public:
87+
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
88+
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
89+
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
90+
// 修改了t1的数值和结构
91+
t1->left = mergeTrees(t1->left, t2->left); // 左
92+
t1->val += t2->val; // 中
93+
t1->right = mergeTrees(t1->right, t2->right); // 右
94+
return t1;
95+
}
96+
};
97+
```
98+
99+
后序遍历呢，依然可以，代码如下：
100+
101+
```
102+
class Solution {
103+
public:
104+
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
105+
if (t1 == NULL) return t2; // 如果t1为空，合并之后就应该是t2
106+
if (t2 == NULL) return t1; // 如果t2为空，合并之后就应该是t1
107+
// 修改了t1的数值和结构
108+
t1->left = mergeTrees(t1->left, t2->left); // 左
109+
t1->right = mergeTrees(t1->right, t2->right); // 右
110+
t1->val += t2->val; // 中
111+
return t1;
112+
}
113+
};
114+
```
115+
116+
**但是前序遍历是最好理解的，我建议大家用前序遍历来做就OK。**
117+
118+
**那么如下还总结了四种方法，递归的方式均使用了前序遍历，此时大家应该知道了，以下每一种递归的方法都可以换成中序和后序遍历，所以本题的解法是很多的。**
119+
120+
**其实这道题目迭代法实现是比较困难的，大家可以试一试，是一道不错的面试进阶题目。**
7121

8122
四种写法如下：
9123

@@ -16,7 +130,7 @@ https://leetcode-cn.com/problems/merge-two-binary-trees/
16130

17131
###递归
18132

19-
修改了输入树的结构
133+
修改了输入树的结构，前序遍历
20134
```
21135
class Solution {
22136
public:
@@ -32,7 +146,7 @@ public:
32146
};
33147
```
34148

35-
不修改输入树的结构
149+
不修改输入树的结构，前序遍历
36150
```
37151
class Solution {
38152
public:
@@ -51,6 +165,7 @@ public:
51165

52166
一波指针的操作，自己写的野路子
53167
想要更改二叉树的值，应该传入指向指针的指针， 如果process(t1, t2);这么写的话，其实只是传入的一个int型的指针，并没有传入地址，要传入指向指针的指针才能完成对t1的修改。
168+
（前序遍历）
54169
```
55170
class Solution {
56171
public:
@@ -77,7 +192,7 @@ public:
77192
```
78193
###迭代
79194

80-
这应该是最简单直观的迭代法了
195+
这应该是最简单直观的迭代法了，模拟的层序遍历。
81196
```
82197
class Solution {
83198
public:

‎problems/0968.监控二叉树.md

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -12,13 +12,13 @@ https://leetcode-cn.com/problems/binary-tree-cameras/
1212

1313
我们之前做动态规划的时候，只要最难的地方在于确定状态转移方程，至于遍历方式无非就是在数组或者二维数组上。
1414

15-
**而本题，不仅要确定状态转移方式，而且要在树上进行推导，所以难度就上来了，一些同学知道这道题目难，但其实说不上难点究竟在哪。**
15+
**本题并不是动态规划，其本质是贪心，但我们要确定状态转移方式，而且要在树上进行推导，所以难度就上来了，一些同学知道这道题目难，但其实说不上难点究竟在哪。**
1616

1717
1. 需要确定遍历方式
1818

1919
首先先确定遍历方式，才能确定转移方程，那么该如何遍历呢？
2020

21-
在安排选择摄像头的位置的时候，**我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的**
21+
在安排选择摄像头的位置的时候，**我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的**，这也是本道贪心的原理所在！
2222

2323
如何从低向上推导呢？
2424

@@ -59,9 +59,11 @@ https://leetcode-cn.com/problems/binary-tree-cameras/
5959
* 1：本节点有摄像头
6060
* 2：本节点有覆盖
6161

62-
大家应该找不出第四个节点的状态了。
62+
大家应该找不出第四个节点的状态了。
6363

64-
那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？
64+
**一些同学可能会想有没有第四种状态：本节点无摄像头，其实无摄像头就是 无覆盖 或者 有覆盖的状态，所以一共还是三个状态。**
65+
66+
**那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？**
6567

6668
回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。
6769

@@ -141,7 +143,7 @@ left == 1 && right == 1 左右节点都有摄像头
141143

142144
这种情况也是大多数同学容易迷惑的情况。
143145

144-
4. 情况4
146+
4. 情况4：头结点没有覆盖
145147

146148
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
147149

‎video/617.合并二叉树.gif

1.64 MB
Loading
2.62 MB
Loading
176 KB
Binary file not shown.
2.28 MB
Loading
171 KB
Binary file not shown.

0 commit comments

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