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

Commit4c2a526

Browse files
Update
1 parent00356b6 commit4c2a526

21 files changed

+577
-67
lines changed

‎README.md‎

Lines changed: 47 additions & 12 deletions
Large diffs are not rendered by default.
104 KB
Loading

‎pics/234.回文链表.png‎

129 KB
Loading
-737 Bytes
Loading

‎pics/763.划分字母区间.png‎

127 KB
Loading

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

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,12 @@ https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorde
33

44
>给出两个序列
55
6+
看完本文，可以一起解决如下两道题目
7+
8+
* 106.从中序与后序遍历序列构造二叉树
9+
* 105.从前序与中序遍历序列构造二叉树
10+
11+
612
#106.从中序与后序遍历序列构造二叉树
713

814
根据一棵树的中序遍历与后序遍历构造二叉树。
@@ -383,7 +389,7 @@ public:
383389
};
384390
```
385391

386-
#105.从前序与中序遍历序列构造二叉树
392+
#105.从前序与中序遍历序列构造二叉树
387393

388394
根据一棵树的前序遍历与中序遍历构造二叉树。
389395

Lines changed: 170 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,122 @@
1+
>构造二叉搜索树，一不小心就平衡了
12
2-
##思路
3+
#108.将有序数组转换为二叉搜索树
34

4-
要考率 和 普通数组转成二叉树有什么差别
5+
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
56

6-
注意这里是构造平衡二叉搜索树，其实 这里不用强调，因为数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从中间取值，不可能随机取，自找麻烦
7+
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
78

8-
一想 这道题目还是有难度的，
9+
示例:
910

10-
一定是递归 分治
11+
![108.将有序数组转换为二叉搜索树](https://img-blog.csdnimg.cn/20201022164420763.png)
1112

12-
循环不变量 的题目列表
13+
#思路
1314

14-
注意答案不是唯一的
15+
做这道题目之前大家可以了解一下这几道：
1516

16-
输入：[-10,-3,0,5,9]
17-
输出：[0,-10,5,null,-3,null,9]
18-
预期结果：[0,-3,9,-10,null,5]
17+
*[106.从中序与后序遍历序列构造二叉树](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)
18+
*[654.最大二叉树](https://mp.weixin.qq.com/s/1iWJV6Aov23A7xCF4nV88w)中其实已经讲过了，如果根据数组构造一颗二叉树。
19+
*[701.二叉搜索树中的插入操作](https://mp.weixin.qq.com/s/lwKkLQcfbCNX2W-5SOeZEA)
20+
*[450.删除二叉搜索树中的节点](https://mp.weixin.qq.com/s/-p-Txvch1FFk3ygKLjPAKw)
21+
22+
23+
进入正题：
24+
25+
题目中说要转换为一棵高度平衡二叉搜索树。这和转换为一棵普通二叉搜索树有什么差别呢？
26+
27+
其实这里不用强调平衡二叉搜索树，数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取，**所以想构成不平衡的二叉树是自找麻烦**。
28+
29+
30+
在[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)和[二叉树：构造一棵最大的二叉树](https://mp.weixin.qq.com/s/1iWJV6Aov23A7xCF4nV88w)中其实已经讲过了，如果根据数组构造一颗二叉树。
31+
32+
**本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间**。
33+
34+
本题其实要比[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg) 和[二叉树：构造一棵最大的二叉树](https://mp.weixin.qq.com/s/1iWJV6Aov23A7xCF4nV88w)简单一些，因为有序数组构造二叉搜索树，寻找分割点就比较容易了。
35+
36+
分割点就是数组中间位置的节点。
37+
38+
那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？
39+
40+
取哪一个都可以，只不过构成了不同的平衡二叉搜索树。
41+
42+
例如：输入：[-10,-3,0,5,9]
43+
44+
如下两棵树，都是这个数组的平衡二叉搜索树：
45+
46+
<imgsrc='../pics/108.将有序数组转换为二叉搜索树.png'width=600> </img></div>
47+
48+
如果要分割的数组长度为偶数的时候，中间元素为两个，是取左边元素 就是树1，取右边元素就是树2。
49+
50+
**这也是题目中强调答案不是唯一的原因。 理解这一点，这道题目算是理解到位了**。
51+
52+
##递归
53+
54+
递归三部曲：
55+
56+
* 确定递归函数返回值及其参数
57+
58+
删除二叉树节点，增加二叉树节点，都是用递归函数的返回值来完成，这样是比较方便的。
59+
60+
相信大家如果仔细看了[二叉树：搜索树中的插入操作](https://mp.weixin.qq.com/s/lwKkLQcfbCNX2W-5SOeZEA)和[二叉树：搜索树中的删除操作](https://mp.weixin.qq.com/s/-p-Txvch1FFk3ygKLjPAKw)，一定会对递归函数返回值的作用深有感触。
61+
62+
那么本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。
63+
64+
再来看参数，首先是传入数组，然后就是左下表left和右下表right，我们在[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)中提过，在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下表来操作原数组。
65+
66+
所以代码如下：
67+
68+
```
69+
// 左闭右闭区间[left, right]
70+
TreeNode* traversal(vector<int>& nums, int left, int right)
71+
```
72+
73+
这里注意，**我这里定义的是左闭右闭区间，在不断分割的过程中，也会坚持左闭右闭的区间，这又涉及到我们讲过的循环不变量**。
74+
75+
在[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)，[35.搜索插入位置](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q) 和[59.螺旋矩阵II](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)都详细讲过循环不变量。
76+
77+
78+
* 确定递归终止条件
79+
80+
这里定义的是左闭右闭的区间，所以当区间 left > right的时候，就是空节点了。
81+
82+
代码如下：
83+
84+
```
85+
if (left > right) return nullptr;
86+
```
87+
88+
* 确定单层递归的逻辑
89+
90+
首先取数组中间元素的位置，不难写出`int mid = (left + right) / 2;`，**这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在[二分法](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)中尤其需要注意！**
91+
92+
所以可以这么写：`int mid = left + ((right - left) / 2);`
93+
94+
但本题leetcode的测试数据并不会越界，所以怎么写都可以。但需要有这个意识！
95+
96+
取了中间位置，就开始以中间位置的元素构造节点，代码：`TreeNode* root = new TreeNode(nums[mid]);`。
97+
98+
接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点。
99+
100+
最后返回root节点，单层递归整体代码如下：
101+
102+
```
103+
int mid = left + ((right - left) / 2);
104+
TreeNode* root = new TreeNode(nums[mid]);
105+
root->left = traversal(nums, left, mid - 1);
106+
root->right = traversal(nums, mid + 1, right);
107+
return root;
108+
```
109+
110+
这里`int mid = left + ((right - left) / 2);`的写法相当于是如果数组长度为偶数，中间位置有两个元素，取靠左边的。
111+
112+
* 递归整体代码如下：
19113

20114
```
21115
class Solution {
22116
private:
23117
TreeNode* traversal(vector<int>& nums, int left, int right) {
24118
if (left > right) return nullptr;
25-
int mid =(left + right) / 2; // 注意越界
119+
int mid = left +((right - left) / 2);
26120
TreeNode* root = new TreeNode(nums[mid]);
27121
root->left = traversal(nums, left, mid - 1);
28122
root->right = traversal(nums, mid + 1, right);
@@ -36,3 +130,68 @@ public:
36130
};
37131
```
38132

133+
**注意：在调用traversal的时候为什么传入的left和right为什么是0和nums.size() - 1，因为定义的区间为左闭右闭**。
134+
135+
136+
##迭代法
137+
138+
迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下表，一个队列放右区间下表。
139+
140+
模拟的就是不断分割的过程，C++代码如下：（我已经详细注释）
141+
142+
```
143+
class Solution {
144+
public:
145+
TreeNode* sortedArrayToBST(vector<int>& nums) {
146+
if (nums.size() == 0) return nullptr;
147+
148+
TreeNode* root = new TreeNode(0); // 初始根节点
149+
queue<TreeNode*> nodeQue; // 放遍历的节点
150+
queue<int> leftQue; // 保存左区间下表
151+
queue<int> rightQue; // 保存右区间下表
152+
nodeQue.push(root); // 根节点入队列
153+
leftQue.push(0); // 0为左区间下表初始位置
154+
rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下表初始位置
155+
156+
while (!nodeQue.empty()) {
157+
TreeNode* curNode = nodeQue.front();
158+
nodeQue.pop();
159+
int left = leftQue.front(); leftQue.pop();
160+
int right = rightQue.front(); rightQue.pop();
161+
int mid = left + ((right - left) / 2);
162+
163+
curNode->val = nums[mid]; // 将mid对应的元素给中间节点
164+
165+
if (left <= mid - 1) { // 处理左区间
166+
curNode->left = new TreeNode(0);
167+
nodeQue.push(curNode->left);
168+
leftQue.push(left);
169+
rightQue.push(mid - 1);
170+
}
171+
172+
if (right >= mid + 1) { // 处理右区间
173+
curNode->right = new TreeNode(0);
174+
nodeQue.push(curNode->right);
175+
leftQue.push(mid + 1);
176+
rightQue.push(right);
177+
}
178+
}
179+
return root;
180+
}
181+
};
182+
```
183+
184+
#总结
185+
186+
**在[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg) 和[二叉树：构造一棵最大的二叉树](https://mp.weixin.qq.com/s/1iWJV6Aov23A7xCF4nV88w)之后，我们顺理成章的应该构造一下二叉搜索树了，一不小心还是一棵平衡二叉搜索树**。
187+
188+
其实思路也是一样的，不断中间分割，然后递归处理左区间，右区间，也可以说是分治。
189+
190+
此时相信大家应该对通过递归函数的返回值来增删二叉树很熟悉了，这也是常规操作。
191+
192+
在定义区间的过程中我们又一次强调了循环不变量的重要性。
193+
194+
最后依然给出迭代的方法，其实就是模拟取中间元素，然后不断分割去构造二叉树的过程。
195+
196+
**就酱，如果对你有帮助的话，也转发给身边需要的同学吧！**
197+

‎problems/0234.回文链表.md‎

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
2+
##题目链接
3+
https://leetcode-cn.com/problems/palindrome-linked-list/
4+
5+
##思路
6+
7+
###数组模拟
8+
9+
最直接的想法，就是把链表装成数组，然后再判断是否回文。
10+
11+
代码也比较简单。如下：
12+
13+
```
14+
class Solution {
15+
public:
16+
bool isPalindrome(ListNode* head) {
17+
vector<int> vec;
18+
ListNode* cur = head;
19+
while (cur) {
20+
vec.push_back(cur->val);
21+
cur = cur->next;
22+
}
23+
// 比较数组回文
24+
for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
25+
if (vec[i] != vec[j]) return false;
26+
}
27+
return true;
28+
}
29+
};
30+
```
31+
32+
上面代码可以在优化，就是先求出链表长度，然后给定vector的初始长度，这样避免vector每次添加节点重新开辟空间
33+
34+
```
35+
class Solution {
36+
public:
37+
bool isPalindrome(ListNode* head) {
38+
39+
ListNode* cur = head;
40+
int length = 0;
41+
while (cur) {
42+
length++;
43+
cur = cur->next;
44+
}
45+
vector<int> vec(length, 0); // 给定vector的初始长度，这样避免vector每次添加节点重新开辟空间
46+
cur = head;
47+
int index = 0;
48+
while (cur) {
49+
vec[index++] = cur->val;
50+
cur = cur->next;
51+
}
52+
// 比较数组回文
53+
for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
54+
if (vec[i] != vec[j]) return false;
55+
}
56+
return true;
57+
}
58+
};
59+
60+
```
61+
62+
###反转后半部分链表
63+
64+
分为如下几步：
65+
66+
* 用快慢指针，快指针有两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置
67+
* 同时用pre记录慢指针指向节点的前一个节点，用来分割链表
68+
* 将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点
69+
* 将后半部分反转 ，得cur2，前半部分为cur1
70+
* 按照cur1的长度，一次比较cur1和cur2的节点数值
71+
72+
如图所示：
73+
74+
<imgsrc='../pics/234.回文链表.png'width=600> </img></div>
75+
76+
代码如下：
77+
78+
```
79+
class Solution {
80+
public:
81+
bool isPalindrome(ListNode* head) {
82+
if (head == nullptr || head->next == nullptr) return true;
83+
ListNode* slow = head; // 慢指针，找到链表中间分位置，作为分割
84+
ListNode* fast = head;
85+
ListNode* pre = head; // 记录慢指针的前一个节点，用来分割链表
86+
while (fast && fast->next) {
87+
pre = slow;
88+
slow = slow->next;
89+
fast = fast->next->next;
90+
}
91+
pre->next = nullptr; // 分割链表
92+
93+
ListNode* cur1 = head; // 前半部分
94+
ListNode* cur2 = reverseList(slow); // 反转后半部分，总链表长度如果是奇数，cur2比cur1多一个节点
95+
96+
// 开始两个链表的比较
97+
while (cur1) {
98+
if (cur1->val != cur2->val) return false;
99+
cur1 = cur1->next;
100+
cur2 = cur2->next;
101+
}
102+
return true;
103+
}
104+
// 反转链表
105+
ListNode* reverseList(ListNode* head) {
106+
ListNode* temp; // 保存cur的下一个节点
107+
ListNode* cur = head;
108+
ListNode* pre = nullptr;
109+
while(cur) {
110+
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
111+
cur->next = pre; // 翻转操作
112+
// 更新pre 和 cur指针
113+
pre = cur;
114+
cur = temp;
115+
}
116+
return pre;
117+
}
118+
};
119+
```
120+
121+
栈
122+

‎problems/0402.移掉K位数字.md‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
2+
##思路
3+
4+
https://www.cnblogs.com/gzshan/p/12560566.html 图不错
5+
6+
有点难度
7+
8+
9+
暴力的解法，其实也不是那么好写的， 首字符去0，k没消耗完，等等这些情况
10+
11+
有点难，卡我很久

0 commit comments

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