题目:请完成一个函数,输入一个二叉树,该函数输出它的镜像。
二叉树节点定义如下:
strcut BinaryTreeNode
{
int val;
strcut BinaryTreeNode* m_pleft;
strcut BinaryTreeNode* m_pright;
}
本题可以参考http://www.cnblogs.com/vpoet/p/4660486.html(Leecode-Invert Binary Tree)一文
实质是递归交换二叉树的左右节点。
比如
/ \
/ \ / \
1.首先查看根节点与左右子节点是否为空,若为空则无需交换
2.先交换根节点的左右子节点。
3.再交换交换后的左子树的左右节点和右子树的左右节点
4.知道到达叶子节点,交换结束。
递归函数如下:
void MirrorRecursively(BinaryTreeNode *pNode)
{
if(pNode==NULL)
return NULL; if(pNode->m_pleft==NULL&&pNode->m_pright==NULL)
return NULL; struct BinaryTreeNode *TempNode;
TempNode=pNode->m_pleft;
pNode->m_pleft=pNode->m_pright;
pNode->m_pright=TempNode; if(pNode->m_pleft)
{
MirrorRecursively(pNode->m_pleft);
} if(pNode->m_pright)
{
MirrorRecursively(pNode->m_pright);
}
}
说明:注意结束条件,到达叶子结点结束
if(pNode->m_pleft==NULL&&pNode->m_pright==NULL)
return NULL;