题目
请完成一个函数，输入一棵二叉树，该函数输出它的镜像。
二叉树结点的定义：
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
};
两棵互为镜像的二叉树如下图
1307402-20180321093450019-1272255336.png
分析
仔细分析这两棵树的特点，可以发现两棵树的根结点相同，但它们的左、右两个子结点相互交换了位置。二叉树镜像的过程如下图
381412-20150831221908669-1524012651.jpg
- （a）交换根结点的左右子树
- （b）交换值为10的结点的左右子结点
- （c）交换值为6的结点的左右子结点
总结：前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，
当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像
算法实现
递归实现
void MirrorRecursively(BinaryTreeNode *pNode) {
if (pNode == nullptr)
return ;
if (pNode->m_pLeft == nullptr && pNode->m_pRight == nullptr)
return ;
BinaryTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
if (pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);
if (pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}
非递归实现
void Mirror(BinaryTreeNode *pRoot) {
if(pRoot == nullptr) return;
// 栈存储结点
stack<BinaryTreeNode*> stackNode;
stackNode.push(pRoot);
// 循环出栈
while(stackNode.size()){
BinaryTreeNode* tree=stackNode.top();
stackNode.pop();
// 交换
if(tree->m_pLeft!=NULL || tree->m_pRight!=NULL){
BinaryTreeNode *ptemp=tree->m_pLeft;
tree->m_pLeft=tree->m_pRight;
tree->m_pRight=ptemp;
}
// 左、右子树结点入栈
if(tree->m_pLeft)
stackNode.push(tree->m_pLeft);
if(tree->m_pRight)
stackNode.push(tree->m_pRight);
}
}
参考
《剑指offer》
