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

Commit3e39d7f

Browse files
Update
1 parent5e2c275 commit3e39d7f

10 files changed

+332
-33
lines changed

‎README.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -114,7 +114,10 @@
114114
*[本周小结！（二叉树系列三）](https://mp.weixin.qq.com/s/JLLpx3a_8jurXcz6ovgxtg)
115115
*[二叉树：合并两个二叉树](https://mp.weixin.qq.com/s/3f5fbjOFaOX_4MXzZ97LsQ)
116116
*[二叉树：二叉搜索树登场！](https://mp.weixin.qq.com/s/vsKrWRlETxCVsiRr8v_hHg)
117+
*[二叉树：我是不是一棵二叉搜索树](https://mp.weixin.qq.com/s/8odY9iUX5eSi0eRFSXFD4Q)
117118
*[二叉树：搜索树的最小绝对差](https://mp.weixin.qq.com/s/Hwzml6698uP3qQCC1ctUQQ)
119+
*[二叉树：我的众数是多少？](https://mp.weixin.qq.com/s/KSAr6OVQIMC-uZ8MEAnGHg)
120+
*[二叉树：公共祖先问题](https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ)
118121

119122

120123

@@ -172,6 +175,7 @@
172175
*[0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
173176
*[0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
174177
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
178+
*[19.删除链表的倒数第N个节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/19.删除链表的倒数第N个节点)
175179
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
176180
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
177181
*[0344.反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
@@ -237,6 +241,7 @@
237241
|[0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)| 数组|中等|**双指针****哈希**|
238242
|[0017.电话号码的字母组合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0017.电话号码的字母组合.md)| 回溯|中等|**回溯**|
239243
|[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)| 数组|中等|**双指针**|
244+
|[0019.删除链表的倒数第N个节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0019.删除链表的倒数第N个节点.md)| 链表|中等|**双指针**|
240245
|[0020.有效的括号](https://github.com/youngyangyang04/leetcode/blob/master/problems/0020.有效的括号.md)| 栈|简单|**栈**|
241246
|[0021.合并两个有序链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0021.合并两个有序链表.md)|链表|简单|**模拟**|
242247
|[0024.两两交换链表中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0024.两两交换链表中的节点.md)|链表|中等|**模拟**|
45.9 KB
Loading
48.2 KB
Loading
47 KB
Loading
58.1 KB
Loading
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2+
3+
##思路
4+
5+
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
6+
7+
思路是这样的，但要注意一些细节。
8+
9+
分为如下几步：
10+
11+
* 首先这里我推荐大家使用虚拟头结点，这样方面处理删除实际头结点的逻辑，如果虚拟头结点不清楚，可以看这篇：[链表：听说用虚拟头节点会方便很多？](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
12+
13+
14+
* 定义fast指针和slow指针，初始值为虚拟头结点，如图：
15+
16+
<imgsrc='../pics/19.删除链表的倒数第N个节点.png'width=600> </img></div>
17+
18+
* fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
19+
<imgsrc='../pics/19.删除链表的倒数第N个节点1.png'width=600> </img></div>
20+
21+
* fast和slow同时移动，之道fast指向末尾，如题：
22+
<imgsrc='../pics/19.删除链表的倒数第N个节点2.png'width=600> </img></div>
23+
24+
* 删除slow指向的下一个节点，如图：
25+
<imgsrc='../pics/19.删除链表的倒数第N个节点3.png'width=600> </img></div>
26+
27+
此时不难写出如下C++代码：
28+
29+
```
30+
class Solution {
31+
public:
32+
ListNode* removeNthFromEnd(ListNode* head, int n) {
33+
ListNode* dummyHead = new ListNode(0);
34+
dummyHead->next = head;
35+
ListNode* slow = dummyHead;
36+
ListNode* fast = dummyHead;
37+
while(n-- && fast != NULL) {
38+
fast = fast->next;
39+
}
40+
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
41+
while (fast != NULL) {
42+
fast = fast->next;
43+
slow = slow->next;
44+
}
45+
slow->next = slow->next->next;
46+
return dummyHead->next;
47+
}
48+
};
49+
```

‎problems/0052.N皇后II.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -43,9 +43,9 @@ void backtracking(int n, int row, vector<string>& chessboard, vector<vector<stri
4343
}
4444
for (int col = 0; col < n; col++) {
4545
if (isValid(row, col, chessboard, n)) {
46-
chessboard[row][col] = 'Q';
46+
chessboard[row][col] = 'Q'; // 放置皇后
4747
backtracking(n, row + 1, chessboard, result);
48-
chessboard[row][col] = '.';
48+
chessboard[row][col] = '.'; // 回溯
4949
}
5050
}
5151
}
Lines changed: 156 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,85 +1,198 @@
11
##链接
22
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
33

4-
##思路
4+
>二叉搜索树的最近公共祖先问题如约而至
5+
6+
#235. 二叉搜索树的最近公共祖先
7+
8+
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
9+
10+
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
11+
12+
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
513

14+
例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
615

7-
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了，可惜二叉树只能自上向低。
16+
![235. 二叉搜索树的最近公共祖先](https://img-blog.csdnimg.cn/20201018172243602.png)
817

9-
那么自上相下查找的话，如何记录祖先呢？
18+
示例 1:
1019

11-
做过[236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)题目的同学，应该知道，只要判断一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。
20+
输入: root =[6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
21+
输出: 6
22+
解释: 节点 2 和节点 8 的最近公共祖先是 6。
23+
示例 2:
24+
25+
输入: root =[6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
26+
输出: 2
27+
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
28+
 
29+
30+
说明:
31+
32+
* 所有节点的值都是唯一的。
33+
* p、q 为不同节点且均存在于给定的二叉搜索树中。
34+
35+
##思路
36+
37+
做过[二叉树：公共祖先问题](https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ)题目的同学应该知道，利用回溯从底向上搜索，遇到一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。
1238

1339
那么本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。
1440

1541
在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
1642

17-
其实只要从上到下遍历的时候，如果 (p->val <= cur->val && cur->val <= q->val)则说明该节点cur就是最近公共祖先了。
43+
其实只要从上到下遍历的时候，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。
44+
45+
理解这一点，本题就很好解了。
46+
47+
和[二叉树：公共祖先问题](https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ)不同，普通二叉树求最近公共祖先需要使用回溯，从底向上来查找，二叉搜索树就不用了，因为搜索树有序（相当于自带方向），那么只要从上向下遍历就可以了。
1848

19-
理解这一点，本题就很好解了。
49+
那么我们可以采用前序遍历（其实这里没有中节点的处理逻辑，遍历顺序无所谓了）。
2050

21-
如图所示
51+
如图所示：p为节点3，q为节点5
2252

2353
<imgsrc='../pics/235.二叉搜索树的最近公共祖先.png'width=600> </img></div>
2454

25-
在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）
55+
可以看出直接按照指定的方向，就可以找到节点4，为最近公共祖先，而且不需要遍历整棵树，找到结果直接返回！
56+
2657

27-
那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历。（因为我们此时不知道p和q谁大，所以两个都要判断）
58+
递归三部曲如下：
59+
60+
* 确定递归函数返回值以及参数
61+
62+
参数就是当前节点，以及两个结点 p、q。
63+
64+
返回值是要返回最近公共祖先，所以是TreeNode * 。
2865

2966
代码如下：
3067

3168
```
32-
if (cur->val > p->val && cur->val > q->val) {
33-
return traversal(cur->left, p, q);
34-
}
69+
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
3570
```
3671

37-
如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历。
72+
* 确定终止条件
73+
74+
遇到空返回就可以了，代码如下：
3875

3976
```
40-
} else if (cur->val < p->val && cur->val < q->val) {
41-
return traversal(cur->right, p, q);
42-
}
77+
if (cur == NULL) return cur;
4378
```
4479

45-
剩下的情况，我们就找到了区间使（p->val <= cur->val && cur->val <= q->val）或者是 （q->val <= cur->val && cur->val <= p->val）
80+
其实都不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。
81+
82+
* 确定单层递归的逻辑
83+
84+
在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）
85+
86+
那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。
87+
88+
**需要注意的是此时不知道p和q谁大，所以两个都要判断**
4689

4790
代码如下：
91+
4892
```
49-
else {
50-
return cur;
51-
}
93+
if (cur->val > p->val && cur->val > q->val) {
94+
TreeNode* left = traversal(cur->left, p, q);
95+
if (left != NULL) {
96+
return left;
97+
}
98+
}
99+
```
100+
101+
**细心的同学会发现，在这里调用递归函数的地方，把递归函数的返回值left，直接return**。
102+
103+
104+
在[二叉树：公共祖先问题](https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ)中，如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。
105+
106+
搜索一条边的写法：
52107

53108
```
109+
if (递归函数(root->left)) return ;
54110
55-
那么整体递归代码如下:
111+
if (递归函数(root->right)) return ;
112+
```
56113

57-
##C++递归代码
114+
搜索整个树写法：
58115

59-
（我这里特意把递归的过程抽出一个函数traversal，这样代码更清晰，有助于读者理解。）
116+
```
117+
left = 递归函数(root->left);
118+
right = 递归函数(root->right);
119+
left与right的逻辑处理;
120+
```
121+
122+
本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。
123+
124+
125+
如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。
126+
127+
```
128+
if (cur->val < p->val && cur->val < q->val) {
129+
TreeNode* right = traversal(cur->right, p, q);
130+
if (right != NULL) {
131+
return right;
132+
}
133+
}
134+
```
135+
136+
剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。
137+
138+
代码如下：
139+
```
140+
return cur;
141+
142+
```
143+
144+
那么整体递归代码如下:
60145

61146
```
62147
class Solution {
63148
private:
64149
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
65-
if (cur->val > p->val && cur->val > q->val) {
66-
return traversal(cur->left, p, q);
67-
} else if (cur->val < p->val && cur->val < q->val) {
68-
return traversal(cur->right, p, q);
69-
} else return cur;
150+
if (cur == NULL) return cur;
151+
// 中
152+
if (cur->val > p->val && cur->val > q->val) { // 左
153+
TreeNode* left = traversal(cur->left, p, q);
154+
if (left != NULL) {
155+
return left;
156+
}
157+
}
158+
159+
if (cur->val < p->val && cur->val < q->val) { // 右
160+
TreeNode* right = traversal(cur->right, p, q);
161+
if (right != NULL) {
162+
return right;
163+
}
164+
}
165+
return cur;
70166
}
71167
public:
72168
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
73-
74169
return traversal(root, p, q);
75170
}
76171
};
77172
```
78173

174+
精简后代码如下：
175+
176+
```
177+
class Solution {
178+
public:
179+
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
180+
if (root->val > p->val && root->val > q->val) {
181+
return lowestCommonAncestor(root->left, p, q);
182+
} else if (root->val < p->val && root->val < q->val) {
183+
return lowestCommonAncestor(root->right, p, q);
184+
} else return root;
185+
}
186+
};
187+
```
188+
189+
##迭代法
190+
191+
对于二叉搜索树的迭代法，大家应该在[二叉树：二叉搜索树登场！](https://mp.weixin.qq.com/s/vsKrWRlETxCVsiRr8v_hHg)就了解了。
79192

80-
##C++迭代法代码
193+
利用其有序性，迭代的方式还是比较简单的，解题思路在递归中已经分析了。
81194

82-
同时给出一个迭代的版本，思想是一样的，代码如下：
195+
迭代代码如下：
83196

84197
```
85198
class Solution {
@@ -96,3 +209,15 @@ public:
96209
}
97210
};
98211
```
212+
213+
灵魂拷问：是不是又被简单的迭代法感动到痛哭流涕？
214+
215+
#总结
216+
217+
对于二叉搜索树的最近祖先问题，其实要比[普通二叉树公共祖先问题](https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ)简单的多。
218+
219+
不用使用回溯，二叉搜索树自带方向性，可以方便的从上向下查找目标区间，遇到目标区间内的节点，直接返回。
220+
221+
最后给出了对应的迭代法，二叉搜索树的迭代法甚至比递归更容易理解，也是因为其有序性（自带方向性），按照目标区间找就行了。
222+
223+
**就酱，学到了，就转发给身边需要学习的同学吧！**

0 commit comments

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