剑指offer之面试题19：二叉树的镜像
题目：
成都创新互联长期为上千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为淄博企业提供专业的网站设计制作、成都网站设计，淄博网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。
操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：
源二叉树
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 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);
}
}
}
};
当前文章：剑指offer之面试题19：二叉树的镜像
文章URL：http://azwzsj.com/article/jhohho.html
