Skip to content

Commit 6aa7278

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent d746885 commit 6aa7278

File tree

5 files changed

+214
-6
lines changed

5 files changed

+214
-6
lines changed

‎README.md

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
# 算法面试思维导图:
2+
3+
![算法面试知识大纲](https://img-blog.csdnimg.cn/20200729181420491.png)
4+
15
# 算法文章精选：
26

37
* [究竟什么是时间复杂度，怎么求时间复杂度，看这一篇就够了](https://mp.weixin.qq.com/s/lYL9TSxLqCeFXIdjt4dcIw)
@@ -34,9 +38,11 @@
3438
|[0053.最大子序和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0053.最大子序和.md) |数组 |简单|**暴力** **贪心** 动态规划 分治|
3539
|[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md) |数组 |中等|**模拟**|
3640
|[0083.删除排序链表中的重复元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0083.删除排序链表中的重复元素.md) |链表 |简单|**模拟**|
37-
|[0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md) |树 |中等|**递归** **栈**|
41+
|[0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md) |树 |中等|**递归** **迭代/栈**|
42+
|[0101.对称二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0101.对称二叉树.md) |树 |简单|**递归** **迭代/栈**|
3843
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md) |链表 |中等|**快慢指针/双指针**|
39-
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md) |树 |中等|**递归** **栈**|
44+
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md) |树 |中等|**递归** **迭代/栈**|
45+
|[0145.二叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/ 0145.二叉树的后序遍历.md) |树 |困难|**递归** **迭代/栈**|
4046
|[0151.翻转字符串里的单词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0151.翻转字符串里的单词.md) |字符串 |中等|**模拟/双指针**|
4147
|[0155.最小栈](https://github.com/youngyangyang04/leetcode/blob/master/problems/0155.最小栈.md) |栈 |简单|**栈**|
4248
|[0202.快乐数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0202.快乐数.md) |哈希表 |简单|**哈希**|

‎problems/0094.二叉树的中序遍历.md

Lines changed: 55 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,10 +3,11 @@ https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
33

44
## 思路
55

6+
题号：94，144，145 一起做一下
67

78
## C++代码
89

9-
递归
10+
### 递归
1011
```
1112
class Solution {
1213
public:
@@ -24,5 +25,58 @@ public:
2425
};
2526
```
2627

28+
### 栈
29+
```
30+
class Solution {
31+
public:
32+
vector<int> inorderTraversal(TreeNode* root) {
33+
vector<int> result;
34+
stack<TreeNode*> st;
35+
TreeNode* cur = root;
36+
while (cur != NULL || !st.empty()) {
37+
if (cur != NULL) {
38+
st.push(cur);
39+
cur = cur->left;
40+
} else {
41+
cur = st.top();
42+
st.pop();
43+
result.push_back(cur->val);
44+
cur = cur->right;
45+
}
46+
}
47+
return result;
48+
}
49+
};
50+
```
51+
52+
### 栈 通用模板
53+
54+
```
55+
class Solution {
56+
public:
57+
vector<int> inorderTraversal(TreeNode* root) {
58+
vector<int> result;
59+
stack<TreeNode*> st;
60+
if (root != NULL) st.push(root);
61+
while (!st.empty()) {
62+
TreeNode* node = st.top();
63+
if (node != NULL) {
64+
st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
65+
if (node->right) st.push(node->right); // 添加右节点
66+
st.push(node); // 添加中节点
67+
st.push(NULL); // 中节点访问过，但是还没有处理，需要做一下标记。
68+
if (node->left) st.push(node->left); // 添加左节点
69+
} else {
70+
st.pop(); // 将空节点弹出
71+
node = st.top(); // 重新取出栈中元素
72+
st.pop();
73+
result.push_back(node->val); // 加入到数组中
74+
}
75+
}
76+
return result;
77+
}
78+
};
79+
```
80+
2781

2882
> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0101.对称二叉树.md

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
## 题目地址
2+
https://leetcode-cn.com/problems/symmetric-tree/
3+
4+
## 思路
5+
6+
7+
## C++代码
8+
9+
### 递归
10+
11+
```
12+
class Solution {
13+
public:
14+
bool compare(TreeNode* left, TreeNode* right) {
15+
if (left == NULL && right != NULL) return false;
16+
else if (left != NULL && right == NULL) return false;
17+
else if (left == NULL && right == NULL) return true;
18+
else if (left->val != right->val) return false;
19+
else return compare(left->left, right->right) && compare(left->right, right->left);
20+
21+
}
22+
bool isSymmetric(TreeNode* root) {
23+
if (root == NULL) return true;
24+
return compare(root->left, root->right);
25+
}
26+
};
27+
```
28+
29+
### 迭代
30+
31+
32+
> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0144.二叉树的前序遍历.md

Lines changed: 31 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
77

88
## C++代码
99

10-
递归
10+
### 递归
1111
```
1212
class Solution {
1313
public:
@@ -25,7 +25,7 @@ public:
2525
};
2626
```
2727

28-
栈
28+
### 栈
2929
```
3030
class Solution {
3131
public:
@@ -46,6 +46,34 @@ public:
4646
};
4747
```
4848

49+
### 栈 通用模板
50+
详细代码注释看 [0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md)
51+
```
52+
class Solution {
53+
public:
54+
vector<int> preorderTraversal(TreeNode* root) {
55+
vector<int> result;
56+
stack<TreeNode*> st;
57+
if (root != NULL) st.push(root);
58+
while (!st.empty()) {
59+
TreeNode* node = st.top();
60+
if (node != NULL) {
61+
st.pop();
62+
if (node->right) st.push(node->right);
63+
if (node->left) st.push(node->left);
64+
st.push(node);
65+
st.push(NULL);
66+
} else {
67+
st.pop();
68+
node = st.top();
69+
st.pop();
70+
result.push_back(node->val);
71+
}
72+
}
73+
return result;
74+
}
75+
};
76+
```
4977

5078

51-
> 更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
79+
> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0145.二叉树的后序遍历.md

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
## 题目地址
2+
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
3+
4+
## 思路
5+
6+
题号：94，144，145 一起做一下
7+
8+
## C++代码
9+
10+
### 递归
11+
12+
```
13+
class Solution {
14+
public:
15+
void traversal(TreeNode* root, vector<int>& vec) {
16+
if (root == NULL) return;
17+
traversal(root->left, vec);
18+
traversal(root->right, vec);
19+
vec.push_back(root->val);
20+
}
21+
vector<int> postorderTraversal(TreeNode* root) {
22+
vector<int> result;
23+
traversal(root, result);
24+
return result;
25+
26+
}
27+
};
28+
```
29+
30+
### 栈
31+
32+
先中右左遍历，然后再反转
33+
34+
```
35+
class Solution {
36+
public:
37+
38+
vector<int> postorderTraversal(TreeNode* root) {
39+
stack<TreeNode*> st;
40+
vector<int> result;
41+
st.push(root);
42+
while (!st.empty()) {
43+
TreeNode* node = st.top();
44+
st.pop();
45+
if (node != NULL) result.push_back(node->val);
46+
else continue;
47+
st.push(node->left);
48+
st.push(node->right);
49+
}
50+
reverse(result.begin(), result.end());
51+
return result;
52+
}
53+
};
54+
```
55+
### 栈 通用模板
56+
57+
详细代码注释看 [0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md)
58+
59+
```
60+
class Solution {
61+
public:
62+
63+
vector<int> postorderTraversal(TreeNode* root) {
64+
vector<int> result;
65+
stack<TreeNode*> st;
66+
if (root != NULL) st.push(root);
67+
while (!st.empty()) {
68+
TreeNode* node = st.top();
69+
if (node != NULL) {
70+
st.pop();
71+
st.push(node);
72+
st.push(NULL);
73+
if (node->right) st.push(node->right);
74+
if (node->left) st.push(node->left);
75+
76+
} else {
77+
st.pop();
78+
node = st.top();
79+
st.pop();
80+
result.push_back(node->val);
81+
}
82+
}
83+
return result;
84+
}
85+
};
86+
```
87+
88+
> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

0 commit comments

Comments
 (0)