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

Commit9ab4d90

Browse files
Update
1 parentd989622 commit9ab4d90

10 files changed

+538
-72
lines changed

‎README.md

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -113,6 +113,7 @@
113113
*[本周小结！（二叉树系列三）](https://mp.weixin.qq.com/s/JLLpx3a_8jurXcz6ovgxtg)
114114
*[二叉树：合并两个二叉树](https://mp.weixin.qq.com/s/3f5fbjOFaOX_4MXzZ97LsQ)
115115
*[二叉树：二叉搜索树登场！](https://mp.weixin.qq.com/s/vsKrWRlETxCVsiRr8v_hHg)
116+
*[二叉树：搜索树的最小绝对差](https://mp.weixin.qq.com/s/Hwzml6698uP3qQCC1ctUQQ)
116117

117118

118119

@@ -268,8 +269,8 @@
268269
|[0110.平衡二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0110.平衡二叉树.md)|树|简单|**递归**|
269270
|[0111.二叉树的最小深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0111.二叉树的最小深度.md)|树|简单|**递归****队列/BFS**|
270271
|[0112.路径总和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0112.路径总和.md)|树|简单|**深度优先搜索/递归****回溯****栈**|
271-
|[0116.填充每个节点的下一个右侧节点指针](https://github.com/youngyangyang04/leetcode/blob/master/problems/0116.填充每个节点的下一个右侧节点指针.md)|二叉树|中等|**广度优先搜索**|
272-
|[0117.填充每个节点的下一个右侧节点指针II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0117.填充每个节点的下一个右侧节点指针II.md)|二叉树|中等|**广度优先搜索**|
272+
|[0116.填充每个节点的下一个右侧节点指针](https://github.com/youngyangyang04/leetcode/blob/master/problems/0116.填充每个节点的下一个右侧节点指针.md)|二叉树|中等|**递归****迭代/广度优先搜索**|
273+
|[0117.填充每个节点的下一个右侧节点指针II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0117.填充每个节点的下一个右侧节点指针II.md)|二叉树|中等|**递归****迭代/广度优先搜索**|
273274
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|
274275
|[0141.环形链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0141.环形链表.md)|链表|简单|**快慢指针/双指针**|
275276
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)|链表|中等|**快慢指针/双指针**|
@@ -325,6 +326,7 @@
325326
|[0637.二叉树的层平均值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0637.二叉树的层平均值.md)|树|简单|**广度优先搜索/队列**|
326327
|[0654.最大二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0654.最大二叉树.md)|树|中等|**递归**|
327328
|[0685.冗余连接II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0685.冗余连接II.md)| 并查集/树/图|困难|**并查集**|
329+
|[0669.修剪二叉搜索树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0669.修剪二叉搜索树.md)| 二叉搜索树/二叉树|简单|**递归****迭代**|
328330
|[0700.二叉搜索树中的搜索](https://github.com/youngyangyang04/leetcode/blob/master/problems/0700.二叉搜索树中的搜索.md)|树|简单|**递归****迭代**|
329331
|[0701.二叉搜索树中的插入操作](https://github.com/youngyangyang04/leetcode/blob/master/problems/0701.二叉搜索树中的插入操作.md)|树|简单|**递归****迭代**|
330332
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**|

‎pics/669.修剪二叉搜索树.png

114 KB
Loading

‎pics/669.修剪二叉搜索树1.png

79.5 KB
Loading

‎problems/0116.填充每个节点的下一个右侧节点指针.md

Lines changed: 63 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,68 @@
44
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
55

66
##思路
7-
同 117题目，代码都是一样的
87

9-
##C++代码
8+
9+
注意题目提示内容，：
10+
* 你只能使用常量级额外空间。
11+
* 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
12+
13+
基本上就是要求使用递归了，迭代的方式一定会用到栈或者队列。
14+
15+
###递归
16+
17+
一想用递归怎么做呢，虽然层序遍历是最直观的，但是递归的方式确实不好想。
18+
19+
如图，假如当前操作的节点是cur：
20+
21+
<imgsrc='../pics/116.填充每个节点的下一个右侧节点指针.png'width=600> </img></div>
22+
23+
最关键的点是可以通过上一层递归 搭出来的线，进行本次搭线。
24+
25+
图中cur节点为元素4，那么搭线的逻辑代码：（**注意注释中操作1和操作2和图中的对应关系**）
26+
27+
```
28+
if (cur->left) cur->left->next = cur->right; // 操作1
29+
if (cur->right) {
30+
if (cur->next) cur->right->next = cur->next->left; // 操作2
31+
else cur->right->next = NULL;
32+
}
33+
```
34+
35+
理解到这里，使用前序遍历，那么不难写出如下代码：
36+
37+
如果对二叉树的前中后序不了解看这篇:[二叉树：一入递归深似海，从此offer是路人](https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA)
38+
39+
40+
```
41+
class Solution {
42+
private:
43+
void traversal(Node* cur) {
44+
if (cur == NULL) return;
45+
// 中
46+
if (cur->left) cur->left->next = cur->right; // 操作1
47+
if (cur->right) {
48+
if (cur->next) cur->right->next = cur->next->left; // 操作2
49+
else cur->right->next = NULL;
50+
}
51+
traversal(cur->left); // 左
52+
traversal(cur->right); // 右
53+
}
54+
public:
55+
Node* connect(Node* root) {
56+
traversal(root);
57+
return root;
58+
}
59+
};
60+
```
61+
62+
###迭代（层序遍历）
63+
64+
本题使用层序遍历是最为直观的，如果对层序遍历不了解，看这篇：[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)。
65+
66+
层序遍历本来就是一层一层的去遍历，记录一层的头结点（nodePre），然后让nodePre指向当前遍历的节点就可以了。
67+
68+
代码如下：
1069

1170
```
1271
@@ -20,9 +79,9 @@ public:
2079
vector<int> vec;
2180
Node* nodePre;
2281
Node* node;
23-
for (int i = 0; i < size; i++) {
82+
for (int i = 0; i < size; i++) { // 开始每一层的遍历
2483
if (i == 0) {
25-
nodePre = que.front(); //取出一层的头结点
84+
nodePre = que.front(); //记录一层的头结点
2685
que.pop();
2786
node = nodePre;
2887
} else {

‎problems/0117.填充每个节点的下一个右侧节点指针II.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@ https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
44

55
##思路
66

7+
这道题目使用递归还是有难度的，不是完美二叉树，应该怎么办。
8+
79
##C++代码
810

911
```

‎problems/0236.二叉树的最近公共祖先.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,6 @@ public:
2121
TreeNode* left = lowestCommonAncestor(root->left, p, q);
2222
TreeNode* right = lowestCommonAncestor(root->right, p, q);
2323
if (left != NULL && right != NULL) return root;
24-
2524
if (left == NULL) return right;
2625
return left;
2726
}

0 commit comments

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