Skip to content

Commit 10f6268

Browse files
MisterBoooMisterBooo
committed
添加更多文章动画
1 parent c1aef7e commit 10f6268

File tree

53 files changed

+4603
-57
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

53 files changed

+4603
-57
lines changed

‎LeetCode 第 1 号问题：两数之和.md

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
# LeetCode 第 1 号问题：两数之和
2+
3+
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 上第 1 号问题：两数之和。题目难度为 Easy，目前通过率为 45.8% 。
8+
9+
### 题目描述
10+
11+
给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。
12+
13+
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
14+
15+
**示例:**
16+
17+
```
18+
给定 nums = [2, 7, 11, 15], target = 9
19+
20+
因为 nums[0] + nums[1] = 2 + 7 = 9
21+
所以返回 [0, 1]
22+
```
23+
24+
### 题目解析
25+
26+
使用查找表来解决该问题。
27+
28+
设置一个 map 容器 record 用来记录元素的值与索引，然后遍历数组 nums。
29+
30+
* 每次遍历时使用临时变量 complement 用来保存目标值与当前值的差值
31+
* 在此次遍历中查找 record ，查看是否有与 complement 一致的值，如果查找成功则返回查找值的索引值与当前变量的值 i
32+
* 如果未找到，则在 record 保存该元素与索引值 i
33+
34+
### 动画描述
35+
36+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20181028221055.gif)
37+
38+
### 代码实现
39+
40+
```
41+
// 1. Two Sum
42+
// https://leetcode.com/problems/two-sum/description/
43+
// 时间复杂度：O(n)
44+
// 空间复杂度：O(n)
45+
class Solution {
46+
public:
47+
vector<int> twoSum(vector<int>& nums, int target) {
48+
unordered_map<int,int> record;
49+
for(int i = 0 ; i < nums.size() ; i ++){
50+
51+
int complement = target - nums[i];
52+
if(record.find(complement) != record.end()){
53+
int res[] = {i, record[complement]};
54+
return vector<int>(res, res + 2);
55+
}
56+
57+
record[nums[i]] = i;
58+
}
59+
}
60+
};
61+
62+
```
63+
64+
65+
66+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎LeetCode 第 101 号问题：对称二叉树.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# LeetCode 第 101 号问题：对称二叉树
2+
3+
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 第 101 号问题：对称二叉树。
8+
9+
### 题目描述
10+
11+
给定一个二叉树，检查它是否是镜像对称的。
12+
13+
例如，二叉树 `[1,2,2,3,4,4,3]` 是对称的。
14+
15+
```
16+
1
17+
/ \
18+
2 2
19+
/ \ / \
20+
3 4 4 3
21+
```
22+
23+
### 题目解析
24+
25+
用递归做比较简单：一棵树是对称的**等价**于它的左子树和右子树两棵树是对称的，问题就转变为判断两棵树是否对称。
26+
27+
### 代码实现
28+
29+
```java
30+
class Solution {
31+
public boolean isSymmetric(TreeNode root) {
32+
if(root == null) return true;
33+
//把问题变成判断两棵树是否是对称的
34+
return isSym(root.left, root.right);
35+
}
36+
//判断的是根节点为r1和r2的两棵树是否是对称的
37+
public boolean isSym(TreeNode r1, TreeNode r2){
38+
if(r1 == null && r2 == null) return true;
39+
if(r1 == null || r2 == null) return false;
40+
//这两棵树是对称需要满足的条件：
41+
//1.俩根节点相等。 2.树1的左子树和树2的右子树，树2的左子树和树1的右子树都得是对称的
42+
return r1.val == r2.val && isSym(r1.left, r2.right)
43+
&& isSym(r1.right, r2.left);
44+
}
45+
}
46+
```
47+
48+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎LeetCode 第 102 号问题：二叉树的层序遍历.md

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
# LeetCode 第 102 号问题：二叉树的层序遍历
2+
3+
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 上第 102 号问题：二叉树的层序遍历。题目难度为 Medium，目前通过率为 55.8% 。
8+
9+
### 题目描述
10+
11+
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
12+
13+
例如:
14+
给定二叉树: `[3,9,20,null,null,15,7]`,
15+
16+
```
17+
3
18+
/ \
19+
9 20
20+
/ \
21+
15 7
22+
```
23+
24+
返回其层次遍历结果：
25+
26+
```
27+
[
28+
[3],
29+
[9,20],
30+
[15,7]
31+
]
32+
```
33+
34+
### 题目解析
35+
36+
该问题需要用到**队列**
37+
38+
- 建立一个queue
39+
- 先把根节点放进去，这时候找根节点的左右两个子节点
40+
- 去掉根节点，此时queue里的元素就是下一层的所有节点
41+
- 用for循环遍历，将结果存到一个一维向量里
42+
- 遍历完之后再把这个一维向量存到二维向量里
43+
- 以此类推，可以完成层序遍历
44+
45+
46+
47+
48+
49+
### 动画描述
50+
51+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20181112084159.gif)
52+
53+
54+
55+
### 代码实现
56+
57+
```
58+
/// BFS
59+
/// Time Complexity: O(n), where n is the number of nodes in the tree
60+
/// Space Complexity: O(n)
61+
class Solution {
62+
public:
63+
vector<vector<int>> levelOrder(TreeNode* root) {
64+
65+
vector<vector<int>> res;
66+
if(root == NULL)
67+
return res;
68+
69+
queue<pair<TreeNode*,int>> q;
70+
q.push(make_pair(root, 0));
71+
72+
while(!q.empty()){
73+
74+
TreeNode* node = q.front().first;
75+
int level = q.front().second;
76+
q.pop();
77+
78+
if(level == res.size())
79+
res.push_back(vector<int>());
80+
assert( level < res.size() );
81+
82+
res[level].push_back(node->val);
83+
if(node->left)
84+
q.push(make_pair(node->left, level + 1 ));
85+
if(node->right)
86+
q.push(make_pair(node->right, level + 1 ));
87+
}
88+
89+
return res;
90+
}
91+
};
92+
93+
```
94+
95+
96+
97+
98+
99+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎LeetCode 第 103 号问题：二叉树的锯齿形层次遍历.md

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
# LeetCode 第 103 号问题：二叉树的锯齿形层次遍历
2+
3+
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 上第 103 号问题：二叉树的锯齿形层次遍历。题目难度为 Medium，目前通过率为 43.8% 。
8+
9+
### 题目描述
10+
11+
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
12+
13+
例如：
14+
给定二叉树 `[3,9,20,null,null,15,7]`,
15+
16+
```
17+
3
18+
/ \
19+
9 20
20+
/ \
21+
15 7
22+
```
23+
24+
返回锯齿形层次遍历如下：
25+
26+
```
27+
[
28+
[3],
29+
[20,9],
30+
[15,7]
31+
]
32+
```
33+
34+
### 题目解析
35+
36+
该问题需要用到**队列**，与之前的[二叉树的层次遍历](https://xiaozhuanlan.com/topic/8579460312)类似，不同点在于在偶数层需要翻转一下。
37+
38+
- 建立一个queue
39+
- 先把根节点放进去，这时候找根节点的左右两个子节点
40+
- 去掉根节点，此时queue里的元素就是下一层的所有节点
41+
- 循环遍历，将结果存到一个一维向量里
42+
- 遍历完之后再把这个一维向量存到二维向量里
43+
- 如果该层为偶数层，则reverse翻转一下
44+
- 以此类推，可以完成层序遍历
45+
46+
### 动画描述
47+
48+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20190502103236.gif)
49+
50+
### 代码实现
51+
52+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20190502103307.png)
53+
54+
55+
56+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎LeetCode 第 107 号问题：二叉树的层次遍历 II.md

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
# LeetCode 第 107 号问题：二叉树的层次遍历 II
2+
3+
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 上第 107 号问题：二叉树的层次遍历 II。题目难度为 Easy，目前通过率为 55.8% 。
8+
9+
### 题目描述
10+
11+
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
12+
13+
例如：
14+
给定二叉树 `[3,9,20,null,null,15,7]`,
15+
16+
```
17+
3
18+
/ \
19+
9 20
20+
/ \
21+
15 7
22+
```
23+
24+
返回其自底向上的层次遍历为：
25+
26+
```
27+
[
28+
[15,7],
29+
[9,20],
30+
[3]
31+
]
32+
```
33+
34+
### 题目解析
35+
36+
该问题需要用到**队列**，解法与上篇[每天一算：Binary Tree Level Order Traversal](https://xiaozhuanlan.com/topic/8579460312)类似，区别在于最后存储方式的不同。
37+
38+
- 建立一个 queue
39+
- 先把根节点放进去，这时候找根节点的左右两个子节点
40+
- 去掉根节点，此时queue里的元素就是下一层的所有节点
41+
- 用 for 循环遍历，将结果存到一个一维向量里
42+
- 遍历完之后再把这个一维向量**插入**到二维向量里
43+
- 以此类推，可以完成层序遍历
44+
45+
46+
47+
### 动画描述
48+
49+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20181112203355.gif)
50+
51+
52+
53+
### 代码实现
54+
55+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/20181112203645.png)
56+
57+
58+
59+
60+
61+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

‎LeetCode 第 110 号问题：平衡二叉树.md

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
# LeetCode 第 110 号问题：平衡二叉树
2+
3+
> 本文首发于公众号「五分钟学算法」，是[图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>)系列文章之一。
4+
>
5+
> 个人网站：[https://www.cxyxiaowu.com](https://www.cxyxiaowu.com)
6+
7+
题目来源于 LeetCode 上第 110 号问题：平衡二叉树。
8+
9+
### 题目描述
10+
11+
给定一个二叉树，判断它是否是高度平衡的二叉树。
12+
13+
### 题目解析
14+
15+
采取**后序遍历**的方式遍历二叉树的每一个结点。
16+
17+
在遍历到一个结点之前已经遍历了它的左右子树，那么只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶结点的路径的长度），就可以一边遍历一边判断每个结点是不是平衡的。
18+
19+
### 动画描述
20+
21+
待补充
22+
23+
### 代码实现
24+
25+
```java
26+
class Solution {
27+
private boolean isBalanced = true;
28+
public boolean isBalanced(TreeNode root) {
29+
getDepth(root);
30+
return isBalanced;
31+
}
32+
public int getDepth(TreeNode root) {
33+
if (root == null)
34+
return 0;
35+
int left = getDepth(root.left);
36+
int right = getDepth(root.right);
37+
if (Math.abs(left - right) > 1) {
38+
isBalanced = false;
39+
}
40+
return right > left ? right + 1 : left + 1;
41+
}
42+
}
43+
```
44+
45+
46+
47+
![](https://bucket-1257126549.cos.ap-guangzhou.myqcloud.com/blog/fz0rq.png)

0 commit comments

Comments
 (0)