本文为剑指 offer 系列第二十篇。
主要知识点为树，给定一棵树来构造它的镜像，用完美的递归逻辑和直观的层序遍历来解决这个问题。
操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
解题思路
思路1
通过观察这个给定的样例可以发现，对于任何一个节点，都是左右子树进行了替换。原来的左子树变成了如今的右子树，而原来的右子树成为了如今的左子树。由于树的结构的特殊性，这就是一个完美的递归思路啊。
思路2
同样还是左右子树来进行替换，我们可以通过层序遍历来依次的获得需要将子树进行替换的节点，然后将子树进行替换。扩展一下，前序遍历中序遍历后序遍历应该都是可以的。
思路3
尝试一下前序遍历来进行替换。写完了我才发现，其实和思路1是相同的道理，只是我们将左右子树的替换单独拿了出来，替换部分其实就类似于我们遍历的时候的cout语句，殊途同归。
解题代码
思路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
| /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *root) {
// 方法1 递归
if(!root) return;
root = helper(root);
}
TreeNode* helper(TreeNode* root){
if(!root) return NULL;
TreeNode *temp = root->left;
root->left = helper(root -> right);
root->right = helper(temp);
return root;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
思路2代码
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
| /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *root) {
//方法二 层序遍历
if(!root) return;
queue<TreeNode*> q{{root}};
while(!q.empty()){
for(int i = q.size();i>0;i--){
TreeNode* a = q.front(); q.pop();
TreeNode* temp = a->left;
a->left = a->right;
a->right = temp;
if(a->left) q.push(a->left);
if(a->right) q.push(a->right);
}
}
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
思路3代码
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
| /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *root) {
//方法3 前序遍历
if(!root) return;
root = preOrder(root);
}
TreeNode* preOrder(TreeNode* root){
if(!root)return NULL;
helper3(root);
if(root->left) preOrder(root->left);
if(root->right) preOrder(root->right);
return root;
}
void helper3(TreeNode* root){
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
}
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！