带你快速刷完67道剑指offer
这是四则或许对你有帮助的讯息
1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档，其中包括往届补录、应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新，帮忙扩散一下。
2、😍 免费分享阿秀个人学习计算机以来的收集到的免费资源，点此白嫖。
3、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。
4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行真的不如一群人报团取暖，过去22届和23届的小伙伴好好跟着走下去的，最后基本都拿到了不错的offer！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。
# No18、二叉树的镜像
# 题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
# 输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 1、借助队列来做，跟上面一题中的迭代版本很像
void Mirror(TreeNode* pRoot) {
if (pRoot == nullptr) return;
queue<TreeNode*> q;
q.push(pRoot);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node)
{
q.push(node->left);
q.push(node->right);
swap(node->left, node->right);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 2、不使用swap函数的迭代版本
void Mirror(TreeNode* pRoot) {
if (pRoot == nullptr) return;
queue<TreeNode*> q;
q.push(pRoot);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node)
{
q.push(node->left);
q.push(node->right);
//swap(node->left, node->right);
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 3、递归版本
void Mirror(TreeNode *pRoot) {
if (pRoot == nullptr) return;
TreeNode* temp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = temp;
Mirror(pRoot->right);
Mirror(pRoot->left);
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 4、栈的迭代版本
void Mirror(TreeNode* pRoot) {
if (pRoot == nullptr) return;
stack<TreeNode*> s;
s.push(pRoot);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node) {
s.push(node->left);
s.push(node->right);
swap(node->left, node->right);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 二刷：
# 1、迭代版本，想多了
运行时间：2ms 占用内存：376k
队列来做，有点类似于层次遍历的意思
void Mirror(TreeNode *pRoot) {//有点类似于二叉树的层次遍历
if(pRoot == nullptr) return;
queue<TreeNode*> q;
TreeNode *node = nullptr;
q.push(pRoot);
while(!q.empty()){
node = q.front();
q.pop();
if(node != nullptr)
{ q.push(node->left);
q.push(node->right);
swap(node->left,node->right);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 2、递归版本，而更容易理解一些，也更好写
运行时间：2ms 占用内存：504k
void Mirror(TreeNode *pRoot) {//有点类似于二叉树的层次遍历
if(pRoot == nullptr) return;
swap(pRoot->left,pRoot->right);
Mirror(pRoot->left);
Mirror(pRoot->right);
}
1
2
3
4
5
6
2
3
4
5
6