题目：
操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：
源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
思路：还是从根结点开始看，根结点，不用交换，看其左右子树，将其交换，然后在交换后的左右子树上，继续看子树的根结点，看这时的左右子树，进行交换；先交换，后递归
从上图看就是
（1）8为根结点 交换左右结点指向（6，10）--->（10，6）
8 8
/ \ / \
6 10 --> 10 6
/ \ / \ / \ / \
5 7 9 11 9 11 5 7
(2)10为根结点 交换左右结点的指向 （9，11）--> (11,9)
8 8
/ \ / \
10 6 --> 10 6
/ \ / \ / \ / \
9 11 5 7 11 9 5 7
(3)6为根结点 交换左右结点的指向 （5，7）--> (7,5)
8 8
/ \ / \
10 6 --> 10 6
/ \ / \ / \ / \
11 9 5 7 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;
}
if(pRoot->left!=NULL||pRoot->right!=NULL)
{
//先交换
TreeNode *left=pRoot->right;
TreeNode *right=pRoot->left;
pRoot->left=left;
pRoot->right=right;
}
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};思路二：利用栈的性质，进行循环访问根结点，交换其左右
代码：
/*
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;
stack<TreeNode*> s1;
s1.push(pRoot);
while(!s1.empty())
{
TreeNode *cur=s1.top();
s1.pop();
//先交换
if(cur->left!=NULL||cur->right!=NULL)
{
TreeNode *left=cur->right;
TreeNode *right=cur->left;
cur->left=left;
cur->right=right;
if(cur->left!=NULL)
s1.push(cur->left);
if(cur->right!=NULL)
s1.push(cur->right);
}
}
}
};免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
