[编程题]二叉树的镜像
• 热度指数：354686 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

##### 输入描述:
```二叉树的镜像定义：源二叉树
8
/  \
6   10
/ \  / \
5  7 9 11
镜像二叉树
8
/  \
10   6
/ \  / \
11 9 7  5```

```/*
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 *pRoot) {
if(pRoot==NULL){
return;
}
TreeNode *tmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmp;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};```

```/* 先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null)
return;
if(root.left == null && root.right == null)
return;

TreeNode pTemp = root.left;
root.left = root.right;
root.right = pTemp;

if(root.left != null)
Mirror(root.left);
if(root.right != null)
Mirror(root.right);
}
}```

```class Solution {
public:
void Mirror(TreeNode *pRoot) {
//递归实现
/*if(pRoot==NULL)
return;
TreeNode *ptemp=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=ptemp;
if(pRoot->left)
Mirror(pRoot->left);
if(pRoot->right)
Mirror(pRoot->right);*/
//非递归实现
if(pRoot==NULL)
return;
stack<TreeNode*> stackNode;
stackNode.push(pRoot);
while(stackNode.size()){
TreeNode* tree=stackNode.top();
stackNode.pop();
if(tree->left!=NULL || tree->right!=NULL){
TreeNode *ptemp=tree->left;
tree->left=tree->right;
tree->right=ptemp;
}
if(tree->left)
stackNode.push(tree->left);
if(tree->right)
stackNode.push(tree->right);
}
}
};```

# python解法：

``````
class Solution:

def Mirror(self, root):
# write code here
if not root:
return root
node=root.left
root.left=root.right
root.right=node
self.Mirror(root.left)
self.Mirror(root.right)
return root
``````

```class Solution {
public:
void Mirror(TreeNode *p) {
if(p){
swap(p -> left, p -> right);
Mirror(p -> left);
Mirror(p -> right);
}
}
};```

```import java.util.Stack;

public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node.left != null||node.right != null){
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
}
}```

```class Solution {
public:
//栈的非递归
void Mirror(TreeNode *pRoot) {
if (pRoot == NULL)return;
stack<TreeNode*> st;
TreeNode* p = NULL;
st.push(pRoot);
while (st.size())
{
p = st.top();
st.pop();
swap(p->left, p->right);
if (p->left)st.push(p->left);
if (p->right)st.push(p->right);
}
}  //队列的非递归
void Mirror(TreeNode *pRoot) {
if (pRoot == NULL)return;
queue<TreeNode*> qu;
TreeNode* p = NULL;
qu.push(pRoot);
while (qu.size())
{
p = qu.front();
qu.pop();
swap(p->left, p->right);
if (p->left)qu.push(p->left);
if (p->right)qu.push(p->right);
}
}
//递归
void Mirror(TreeNode *pRoot) {
if (pRoot == NULL)return;
swap(pRoot->left, pRoot->right);
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};```

## 我的答案

``````public class Solution {
public void Mirror(TreeNode root) {
reverseTree(root);
}

private void reverseTree(TreeNode root){
//为空则结束
if(root == null){
return;
}
//假设root两边的子树自己都已经翻转成功了，那么只需要再将左右子树互换一下就成功了
//交换root的左右子树
swap(root);

//左右子树翻转自己去处理就行了，我们规定每个子树的root都跟最终的root处理方式一样即可
reverseTree(root.left);
reverseTree(root.right);
}

private void swap(TreeNode root){
TreeNode node = null;
node = root.left;
root.left = root.right;
root.right = node;
}
}``````

```//非递归, 层次遍历+swap
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if (!pRoot) return;
vector<TreeNode*> vv;
vv.push_back(pRoot);
while (!vv.empty()) {
vector<TreeNode*> t;
for (auto &i : vv) {
swap(i->left, i->right);
if (i->left) t.push_back(i->left);
if (i->right) t.push_back(i->right);
}
vv.swap(t);
}
}
};```

1. 解法
//自上而下的递归调用
void Mirror(TreeNode *pRoot) {
if(pRoot != NULL){
//先交换当前节点的两个子树节点
TreeNode *tmpNode = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmpNode;
//对交换后的节点做同样的事。
Mirror(pRoot->left);
Mirror(pRoot->right);
}
}

2.我觉得这题和《剑指offer》中的42题（字符串操作）思路有点像:
42题要求翻转单词顺序："I am a student."  ->  "student. a am I"
第一步：翻转所有的字符，eg: "I am a student."  ->  ".tneduts a ma I"
第二步：再翻转每个单词中的顺序，eg:  ".tneduts a ma I"  ->   "student. a am I"

3.其他相近的树操作的题目：
对称树：https://leetcode.com/problems/symmetric-tree/#/description
相等树：https://leetcode.com/problems/same-tree/#/description

```Python解法：
class Solution:
def Mirror(self, root):
# write code here
if root:#如果存在根节点
root.left,root.right=root.right,root.left#根节点左右交换，俩变量交换也可以这样写
self.Mirror(root.left)#递归调用左节点
self.Mirror(root.right)#递归调用右节点
return root#返回节点
else:
return #else无节点时直接return
```

## 递归解法(JavaScript)

```function Mirror(root)
{
if(root === null) return root;
[root.left, root.right] = [root.right, root.left];
Mirror(root.left);
Mirror(root.right);
}```

## 非递归解法

```function Mirror(root)
{
if(root === null) return root;
let stack = [root];
while(stack.length){
let x = stack.pop();
[x.left, x.right] = [x.right, x.left];
if(x.left) stack.push(x.left);
if(x.right) stack.push(x.right);
}
}```

public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
Mirror(root.left);
Mirror(root.right);
TreeNode temp = root.left;
root.left=root.right;
root.right = temp;
}
}
}

```class Solution {
public:
void Mirror(TreeNode *p)
{
if(p==NULL) return;
TreeNode *tmp=p->left;
p->left=p->right;
p->right=tmp;
Mirror(p->left);
Mirror(p->right);
}
};```

//凡是二叉树相关的问题一定要好好理解二叉树的递归定义，
void Mirror(TreeNode *pRoot) {
if (pRoot == NULL)
return;
//交换左右孩子的次序可以在递归之前，也可以在递归之后，但是感觉在递归之后比较好
TreeNode *ptemp;
ptemp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = ptemp;
Mirror(pRoot->left);
Mirror(pRoot->right);
return ;
}

public void Mirror(TreeNode root) {
if(root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}

```class Solution {
public:
void Mirror(TreeNode *p) {
if(!p) return ;
Mirror(p->left);
Mirror(p->right);
swap(p->left,p->right);
}
};```

```class Solution {
public:
void Mirror(TreeNode *pRoot) {
if (pRoot==NULL || (pRoot->left==NULL && pRoot->right==NULL)) {
return;
}
TreeNode *treeTemp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = treeTemp;
if(pRoot->left)
Mirror(pRoot->left);
if(pRoot->right)
Mirror(pRoot->right);
}
};
```

```public class Solution {
public static void Mirror(TreeNode root) {
swapLeftAndRight(root);
}

public static void swapLeftAndRight(TreeNode root){
if (root == null){
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
TreeNode temp = right;
root.right = left;
root.left = temp;
swapLeftAndRight(root.left);
swapLeftAndRight(root.right);
}
}```
1、             8
/    \
6       10
/     \    /     \
5      7  9     11
2、
8
/    \
10       6
/     \    /     \
9      11 5     7
3、
8
/    \
10       6
/     \    /     \
11     9  7     5

```递归方法
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == nullptr)
return;
swap(pRoot->left, pRoot->right);

Mirror(pRoot->left);
Mirror(pRoot->right);
}
};
```

```非递归
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == nullptr)
return;
queue<TreeNode*> q;
q.push(pRoot);
while(!q.empty())
{
TreeNode* t = q.front();
q.pop();
if(t->left != nullptr)
q.push(t->left);
if(t->right != nullptr)
q.push(t->right);
TreeNode* tmp = t->left;
t->left = t->right;
t->right = tmp;
}
}
};```

1509条回答 95186浏览

# 通过挑战的用户

• 2019-12-15 12:58:37
• 2019-12-15 12:55:48
• 2019-12-15 12:37:03
• 2019-12-15 12:26:02
• 2019-12-15 12:05:33

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题