lc94_二叉树的中序遍历 TED_为什么70%的成功者都是性格内向 高性能内存分配器 jemalloc 基本原理 电视高清直播资源设置
Algorithm
lc94_二叉树的中序遍历
思路: 直接递归遍历。
自己的写法有点丑，没有引用，还是看下面的题解的递归遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (!root) {
return ans;
}
if (root->left) {
auto tmp = inorderTraversal(root->left);
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
ans.emplace_back(root->val);
if (root->right) {
auto tmp = inorderTraversal(root->right);
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
return ans;
}
};
|
题解递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
};
|
题解迭代法
模拟函数堆栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
|
Morris 中序遍历
其他两种方法要么使用函数递归栈O(n)，要么自己模拟栈O(n).
而这里 Morris 遍历则会进行两次遍历，从而做到不算答案的vector下使用O(1)的空间.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *predecessor = nullptr;
while (root != nullptr) {
if (root->left != nullptr) {
// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
predecessor = root->left;
while (predecessor->right != nullptr && predecessor->right != root) {
predecessor = predecessor->right;
}
// 让 predecessor 的右指针指向 root，继续遍历左子树
if (predecessor->right == nullptr) {
predecessor->right = root;
root = root->left;
}
// 说明左子树已经访问完了，我们需要断开链接
else {
res.push_back(root->val);
predecessor->right = nullptr;
root = root->right;
}
}
// 如果没有左孩子，则直接访问右孩子
else {
res.push_back(root->val);
root = root->right;
}
}
return res;
}
};
|
Review
TED_为什么70%的成功者都是性格内向
学校教育，社会教育都鼓励外向。
但是实际上内向的人更多时间独处进行一些深度思考，也更容易接收他人的意见。
所以善待内向的人。 然后内向的人也可以多尝试把知道的知识分享贡献给世界。
Tips
高性能内存分配器 jemalloc 基本原理
Share
电视高清直播资源设置
回家给家里电视装了一下高清直播央视卫视资源
让家里的4K电视成为真正的4K电视。
而不是傻逼爱奇艺，腾讯视频广告盒😅
不用U盘，超级简单。
- 电脑安装 my-tv
- 用电脑打开欢视助手 传输安装apk就可以
电视安装欢视助手比较简单，自行谷歌