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

Commitb872cf6

Browse files
Update
1 parent865f054 commitb872cf6

10 files changed

+144
-9
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -90,6 +90,8 @@
9090
*[本周小结！（二叉树）](https://mp.weixin.qq.com/s/JWmTeC7aKbBfGx4TY6uwuQ)
9191
*[二叉树：我对称么？](https://mp.weixin.qq.com/s/Kgf0gjvlDlNDfKIH2b1Oxg)
9292
*[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)
93+
*[二叉树：看看这些树的最小深度](https://mp.weixin.qq.com/s/BH8-gPC3_QlqICDg7rGSGA)
94+
9395

9496
（持续更新中....）
9597

@@ -286,6 +288,7 @@
286288
|[0538.把二叉搜索树转换为累加树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0538.把二叉搜索树转换为累加树.md)|二叉树|简单|**递归****迭代**|
287289
|[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)|字符串|简单|**模拟**|
288290
|[0559.N叉树的最大深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0559.N叉树的最大深度.md)|N叉树|简单|**递归**|
291+
|[0572.另一个树的子树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0572.另一个树的子树.md)|二叉树|简单|**递归**|
289292
|[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)|哈希表|简单|**哈希**|
290293
|[0589.N叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0589.N叉树的前序遍历.md)|树|简单|**递归****栈/迭代**|
291294
|[0590.N叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0590.N叉树的后序遍历.md)|树|简单|**递归****栈/迭代**|

‎pics/110.平衡二叉树.png

8.99 KB
Loading

‎pics/110.平衡二叉树1.png

10.5 KB
Loading
14.9 KB
Loading

‎problems/0110.平衡二叉树.md

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,34 @@
11
##题目地址
22
https://leetcode-cn.com/problems/balanced-binary-tree/
33

4+
#110.平衡二叉树
5+
6+
给定一个二叉树，判断它是否是高度平衡的二叉树。
7+
8+
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
9+
10+
示例 1:
11+
12+
给定二叉树[3,9,20,null,null,15,7]
13+
14+
<imgsrc='../pics/110.平衡二叉树.png'width=600> </img></div>
15+
16+
返回 true 。
17+
18+
示例 2:
19+
20+
给定二叉树[1,2,2,3,3,null,null,4,4
21+
22+
<imgsrc='../pics/110.平衡二叉树1.png'width=600> </img></div>
23+
24+
返回 false 。
25+
426
##思路
527

28+
分析一下这道题是不是和求深度很像，在[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)中是求左右子树的最大深度，本题呢，是要求左右子树高度差绝对值不超过1。
29+
30+
31+
632
递归三步曲分析：
733

834
1. 明确递归函数的参数和返回值

‎problems/0113.路径总和II.md

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@
2626
为了尽可能的把回溯过程体现出来，我写出如下代码（**这个代码一定不是最简洁的，但是比较清晰的，过于简洁的代码不方便读者理解**）
2727

2828

29-
##C++代码
29+
##回溯C++代码
3030

3131
```
3232
class Solution {
@@ -70,3 +70,7 @@ public:
7070
}
7171
};
7272
```
73+
74+
这道题目也可以用迭代法，相对于112.路径总和，每个节点不仅要保存当前路径和，也要保存当前路径，其实比较麻烦，也没有必要，因为回溯法虽然也是递归，但是如果用迭代来实现回溯法的话，是很费劲的，因为回溯的过程需要用栈模拟出来非常麻烦。
75+
76+
这也是为什么我在后面讲解回溯算法的时候，都是使用递归，也没有人会有栈模拟回溯算法（自己找麻烦，哈哈）。

‎problems/0222.完全二叉树的节点个数.md

Lines changed: 82 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,80 @@
11
##题目地址
22
https://leetcode-cn.com/problems/count-complete-tree-nodes/
33

4-
##思路
4+
>今天是中秋&&国庆，所以来一道二叉树简单题吧
55
6-
没有必要强调是完全二叉树，就是求二叉树节点的个数，当然还是递归法和迭代法。
6+
如果之前两篇[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)，[二叉树：看看这些树的最小深度](https://mp.weixin.qq.com/s/BH8-gPC3_QlqICDg7rGSGA)都认真看了的话，这道题目可以分分钟刷掉了哈哈。
77

8-
这道题目的递归法和求二叉树的深度写法类似， 而迭代法：二叉树广度优先遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
8+
#222.完全二叉树的节点个数
99

10-
![完全二叉树](https://img-blog.csdnimg.cn/20200810164440999.png)
10+
给出一个完全二叉树，求出该树的节点个数。
11+
12+
示例:
13+
14+
<imgsrc='../pics/222.完全二叉树的节点个数.png'width=600> </img></div>
15+
16+
#思路
17+
18+
这道题目其实没有必要强调是完全二叉树，就是求二叉树节点的个数。
19+
20+
![image.png](https://pic.leetcode-cn.com/168a07d49c103ada57202f5ad60a2d51f3d0e0ea5c8399e1caed81b709153c85-image.png)
21+
22+
依然可以使用递归法和迭代法来解决。
23+
24+
这道题目的递归法和求二叉树的深度写法类似， 而迭代法：二叉树层序遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
25+
26+
递归遍历的顺序依然是后序（左右中）。
27+
28+
##递归
29+
30+
如果对求二叉树深度还不熟悉的话，看这篇：[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)。
31+
32+
1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
33+
34+
代码如下：
35+
```
36+
int getNodesNum(TreeNode* cur) {
37+
```
38+
39+
2. 确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
40+
41+
代码如下：
42+
43+
```
44+
if (cur == NULL) return 0;
45+
```
46+
47+
3. 确定单层递归的逻辑：先求它的左子树的节点数量，再求的右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
1148

1249
代码如下：
1350

14-
##C++代码
51+
```
52+
int leftNum = getNodesNum(cur->left); // 左
53+
int rightNum = getNodesNum(cur->right); // 右
54+
int treeNum = leftNum + rightNum + 1; // 中
55+
return treeNum;
56+
```
57+
58+
所以整体C++代码如下：
59+
60+
```
61+
class Solution {
62+
private:
63+
int getNodesNum(TreeNode* cur) {
64+
if (cur == 0) return 0;
65+
int leftNum = getNodesNum(cur->left); // 左
66+
int rightNum = getNodesNum(cur->right); // 右
67+
int treeNum = leftNum + rightNum + 1; // 中
68+
return treeNum;
69+
}
70+
public:
71+
int countNodes(TreeNode* root) {
72+
return getNodesNum(root);
73+
}
74+
};
75+
```
1576

16-
###递归
77+
代码精简之后C++代码如下：
1778
```
1879
class Solution {
1980
public:
@@ -22,11 +83,14 @@ public:
2283
return 1 + countNodes(root->left) + countNodes(root->right);
2384
}
2485
};
86+
2587
```
2688

27-
###迭代-广度优先
89+
##迭代法
90+
91+
如果对求二叉树层序遍历还不熟悉的话，看这篇：[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)。
2892

29-
二叉树层序遍历模板详解：[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)
93+
那么只要模板少做改动，加一个变量result，统计节点数量就可以了
3094

3195
```
3296
class Solution {
@@ -50,4 +114,14 @@ public:
50114
};
51115
```
52116

117+
#总结
118+
119+
这道题目的解法其实我们在[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)和[二叉树：看看这些树的最小深度](https://mp.weixin.qq.com/s/BH8-gPC3_QlqICDg7rGSGA)都有提到过了。
120+
121+
一样的分析套路，代码也差不多，估计此时大家最这一类求二叉树节点数量以及求深度应该非常熟练了。
122+
123+
没有做过这道题目的同学可以愉快的刷了它了。
124+
125+
最后祝大家中秋&国庆节日愉快哈！
126+
53127
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0257.二叉树的所有路径.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -183,6 +183,7 @@ public:
183183
```
184184

185185
##C++代码第二种写法
186+
186187
接下来我介绍另一种写法，如下写法就是一个标准的前序遍历的过程。
187188

188189
```
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
2+
3+
4+
##C++代码
5+
6+
```
7+
class Solution {
8+
public:
9+
bool compare(TreeNode* left, TreeNode* right) {
10+
if (left == NULL && right != NULL) return false;
11+
else if (left != NULL && right == NULL) return false;
12+
else if (left == NULL && right == NULL) return true;
13+
else if (left->val != right->val) return false;
14+
else return compare(left->left, right->left) && compare(left->right, right->right);
15+
16+
}
17+
bool isSubtree(TreeNode* s, TreeNode* t) {
18+
if (s == NULL) return false;
19+
if (compare(s, t)) return true;
20+
if(isSubtree(s->left, t)) return true;
21+
if (isSubtree(s->right, t)) return true;
22+
return false;
23+
}
24+
};
25+
```
Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
2+
面试题02.07.链表相交 重复题目

0 commit comments

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