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

Commitcda3787

Browse files
Update
1 parenta3a02ad commitcda3787

7 files changed

+356
-9
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -82,6 +82,8 @@
8282

8383
* 二叉树
8484
*[关于二叉树，你该了解这些！](https://mp.weixin.qq.com/s/_ymfWYvTNd2GvWvC5HOE4A)
85+
*[二叉树：一入递归深似海，从此offer是路人](https://mp.weixin.qq.com/s/PwVIfxDlT3kRgMASWAMGhA)
86+
*[二叉树：听说递归能做的，栈也能做！](https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg)
8587

8688
（持续更新中....）
8789

@@ -214,6 +216,7 @@
214216
|[0107.二叉树的层次遍历II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0107.二叉树的层次遍历II.md)|树|简单|**广度优先搜索/队列/BFS**|
215217
|[0110.平衡二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0110.平衡二叉树.md)|树|简单|**递归**|
216218
|[0111.二叉树的最小深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0111.二叉树的最小深度.md)|树|简单|**递归****队列/BFS**|
219+
|[0112.路径总和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0112.路径总和.md)|树|简单|**深度优先搜索/递归****回溯****栈**|
217220
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|
218221
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)|链表|中等|**快慢指针/双指针**|
219222
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)|树|中等|**递归****迭代/栈**|

‎pics/112.路径总和.png

100 KB
Loading
43.7 KB
Loading
113 KB
Loading

‎problems/0112.路径总和.md

Lines changed: 74 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,49 @@
11
##题目地址
22

33
##思路
4-
// 遍历单条边，还是遍历整个树，取最优数值！！
5-
// 对啊，用sum来减法啊，免得多定义一个变量
64

7-
##C++
5+
相信大家看到千篇一律的写法：
6+
```
7+
class Solution {
8+
public:
9+
bool hasPathSum(TreeNode* root, int sum) {
10+
if (root == NULL) return false;
11+
if (!root->left && !root->right && sum == root->val) {
12+
return true;
13+
}
14+
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
15+
}
16+
};
17+
```
18+
**这种写法简短是简短，但其实对于读者理解不是很友好，没有很好的体现出递归的顺序已经背后的回溯。**
19+
20+
**相信很多同学都疑惑递归的过程中究竟什么时候需要返回值，什么时候不需要返回值？**
821

9-
贼粗糙的写法
22+
**如果需要搜索整颗二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。**
1023

11-
深度优先遍历
24+
而本题就要要搜索一条路径，使其上所有节点值相加等于目标和，所以递归需要返回值！
25+
26+
如图所示：
27+
28+
<imgsrc='../pics/112.路径总和.png'width=600> </img></div>
29+
30+
图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。
31+
32+
那么使用深度优先遍历的方式（本题前中后序都可以，无所谓）来遍历二叉树，如下代码我尽量将每一步清晰的表现出来，C++代码如下：
1233

1334
```
1435
class Solution {
1536
private:
1637
bool traversal(TreeNode* cur, int count) {
1738
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
18-
if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
39+
40+
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回
1941
20-
if (cur->left) { // 左
42+
if (cur->left) { // 左 （空节点不遍历）
2143
// 遇到叶子节点返回true，则直接返回true
2244
if (traversal(cur->left, count - cur->left->val)) return true;
2345
}
24-
if (cur->right) { // 右
46+
if (cur->right) { // 右 （空节点不遍历）
2547
// 遇到叶子节点返回true，则直接返回true
2648
if (traversal(cur->right, count - cur->right->val)) return true;
2749
}
@@ -36,7 +58,8 @@ public:
3658
};
3759
```
3860

39-
其实本题一定是有回溯的，没有回溯，如果后撤重新找另一条路径呢，但是貌似以上代码中，**大家貌似没有感受到回溯，那是因为回溯在代码里隐藏起来了。**
61+
62+
那么其实本题一定是有回溯的，没有回溯，如何后撤重新找另一条路径呢，但是貌似以上代码中，**大家貌似没有感受到回溯，那是因为回溯在代码里隐藏起来了。**
4063

4164
隐藏在`traversal(cur->left, count - cur->left->val)`这里， 因为把`count - cur->left->val` 直接作为参数传进去，函数结束，count自然恢复到原先的数值了。
4265

@@ -79,3 +102,45 @@ public:
79102
}
80103
};
81104
```
105+
106+
如果使用栈模拟递归的话，那么如果做回溯呢？
107+
108+
此时栈里一个元素不仅要记录该节点指针，还要记录从头结点到该节点的路径数值总和。
109+
110+
C++就我们用pair结构来存放这个栈里的元素。
111+
112+
定义为：`pair<TreeNode*, int>` pair<节点指针，路径数值>
113+
114+
这个为栈里的一个元素。
115+
116+
如下代码是使用栈模拟的前序遍历，如下：（详细注释）
117+
118+
```
119+
class Solution {
120+
121+
public:
122+
bool hasPathSum(TreeNode* root, int sum) {
123+
if (root == NULL) return false;
124+
// 此时栈里要放的是pair<节点指针，路径数值>
125+
stack<pair<TreeNode*, int>> st;
126+
st.push(pair<TreeNode*, int>(root, root->val));
127+
while (!st.empty()) {
128+
pair<TreeNode*, int> node = st.top();
129+
st.pop();
130+
// 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
131+
if (!node.first->left && !node.first->right && sum == node.second) return true;
132+
133+
// 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
134+
if (node.first->right) {
135+
st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));
136+
}
137+
138+
// 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
139+
if (node.first->left) {
140+
st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));
141+
}
142+
}
143+
return false;
144+
}
145+
};
146+
```
Lines changed: 179 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,179 @@
1+
##题目地址
2+
3+
https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/
4+
5+
#思路
6+
7+
8+
##暴力统计
9+
10+
这看到这道题目，最直观的方法一定是把这个树都遍历了，用map统计频率，用vector排个序，最后出去前面高频的元素。
11+
12+
其实这是可以的，也是有效的，面试中时间紧张，可能快速的把这个方法实现出来，后面在考虑满满优化。
13+
14+
15+
至于用前中后序那种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！
16+
17+
这种方法C++代码如下：
18+
19+
20+
```
21+
class Solution {
22+
private:
23+
24+
void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
25+
if (cur == NULL) return ;
26+
map[cur->val]++; // 统计元素频率
27+
searchBST(cur->left, map);
28+
searchBST(cur->right, map);
29+
return ;
30+
}
31+
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
32+
return a.second > b.second;
33+
}
34+
public:
35+
vector<int> findMode(TreeNode* root) {
36+
unordered_map<int, int> map;
37+
vector<int> result;
38+
if (root == NULL) return result;
39+
searchBST(root, map);
40+
vector<pair<int, int>> vec(map.begin(), map.end());
41+
sort(vec.begin(), vec.end(), cmp); // 给频率排个序
42+
result.push_back(vec[0].first);
43+
for (int i = 1; i < vec.size(); i++) {
44+
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
45+
else break;
46+
}
47+
return result;
48+
}
49+
};
50+
```
51+
52+
**这种方法的缺点是没有利用上二叉搜索树这一特性**，如果用这种方法，这道题就可以是普通的二叉树就行了，反正都要全撸一遍统计频率。
53+
54+
##中序遍历
55+
56+
既然是搜索树，它就是有序的，那么如何有序呢？
57+
58+
**搜索树在中序遍历的过程中，就是有序序列，所以此时的问题相当于 给出如果给出一个有序数组，求最大频率的元素集合。**
59+
60+
**所以我们要采用中序遍历！**
61+
62+
如图：
63+
64+
<imgsrc='../pics/501.二叉搜索树中的众数1.png'width=600> </img></div>
65+
66+
中序遍历代码如下：
67+
68+
```
69+
void searchBST(TreeNode* cur) {
70+
if (cur == NULL) return ;
71+
searchBST(cur->left); // 左
72+
（处理节点） // 中
73+
searchBST(cur->right); // 右
74+
return ;
75+
}
76+
```
77+
78+
遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，要是数组的话，好搞，在树上怎么搞呢？
79+
80+
需要弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。
81+
82+
而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素，然后再给pre赋值即pre = cur;
83+
84+
代码如下：
85+
86+
```
87+
if (pre == NULL) { // 第一个节点
88+
count = 1;
89+
} else if (pre->val == cur->val) { // 与前一个节点数值相同
90+
count++;
91+
} else { // 与前一个节点数值不同
92+
count = 1;
93+
}
94+
pre = cur; // 更新上一个节点
95+
```
96+
97+
此时又有问题了，因为要求最大频率的元素集合，直观想的想法是要先遍历一遍找出频率最大的次数maxCount，然后在重新遍历一遍再把出现频率为maxCount的元素放进集合。
98+
99+
100+
那么如何只遍历一遍呢？
101+
102+
如果 频率count 等于 maxCount，当然要把这个元素加入到结果集中（以下代码为result数组），代码如下：
103+
104+
```
105+
if (count == maxCount) { // 如果和最大值相同，放进result中
106+
result.push_back(cur->val);
107+
}
108+
```
109+
110+
当时感觉这里有问题，result怎么能轻易就把元素放进去了呢，万一，这个maxCount此时还不是真正最大值呢。
111+
112+
所以下面要做如下操作：
113+
114+
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。
115+
116+
```
117+
if (count > maxCount) { // 如果计数大于最大值
118+
maxCount = count;
119+
result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
120+
result.push_back(cur->val);
121+
}
122+
```
123+
124+
关键代码都讲完了，完整代码如下：
125+
126+
127+
```
128+
class Solution {
129+
private:
130+
int count;
131+
int maxCount;
132+
TreeNode* pre;
133+
vector<int> result;
134+
void searchBST(TreeNode* cur) {
135+
if (cur == NULL) return ;
136+
137+
searchBST(cur->left); // 左
138+
// 中
139+
if (pre == NULL) { // 第一个节点
140+
count = 1;
141+
} else if (pre->val == cur->val) { // 与前一个节点数值相同
142+
count++;
143+
} else { // 与前一个节点数值不同
144+
count = 1;
145+
}
146+
pre = cur; // 更新上一个节点
147+
148+
if (count == maxCount) { // 如果和最大值相同，放进result中
149+
result.push_back(cur->val);
150+
}
151+
152+
if (count > maxCount) { // 如果计数大于最大值
153+
maxCount = count;
154+
result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
155+
result.push_back(cur->val);
156+
}
157+
158+
searchBST(cur->right); // 右
159+
return ;
160+
}
161+
162+
public:
163+
vector<int> findMode(TreeNode* root) {
164+
int count = 0; // 记录元素出现次数
165+
int maxCount = 0;
166+
TreeNode* pre = NULL; // 记录前一个节点
167+
result.clear();
168+
169+
searchBST(root);
170+
return result;
171+
}
172+
};
173+
```
174+
175+
此时的运行效率：
176+
177+
<imgsrc='../pics/501.二叉搜索树中的众数.png'width=600> </img></div>
178+
179+
**需要强调的是 leetcode上的耗时统计是非常不准确的，看个大概就行，一样的代码耗时可以差百分之50以上**，所以leetcode的耗时统计别太当回事，知道理论上的效率优劣就行了。

0 commit comments

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