首页 > 代码库 > 二叉树的镜像

二叉树的镜像

题目:完成一个函数,输入一个二叉树,该函数输出它的镜像

分析:何为镜像?

image

首先我们先去遍历头结点,如果不为空,那么我们就要继续遍历其左子树和右子树,如果不为空就进行一个交换,这里要说明的是:树的根节点与其左右子树之间是采用指针的形式进行一个连接的,也就是你交换了左右子树(比如 10 6),但是子树(10,6)下面对应的子树(比如10 对应11,9,  6对应7,5)之间的连接是不变的。

直到其左右子树为空的时候就停止。

给定一个二叉树的结点定义:

struct BinaryTreeNode{
    int m_pValue;
    BinaryTreeNode *m_leftTreeNode;
    BinaryTreeNode *m_rightTreeNode;
};

如何输出它的镜像输出?

BinaryTreeNode* mirrorRecursively(BinaryTreeNode *pNode)
{
    if(pNode==NULL)
        return NULL;
    BinaryTreeNode *mirrorTree=NULL;
    if(pNode->m_leftTreeNode!=NULL&&pNode->m_rightTreeNode!=NULL)  
    {
       BinaryTreeNode *tempTree=pNode->m_leftTreeNode;
       pNode->m_leftTreeNode=pNode->m_rightTreeNode;
       pNode->m_rightTreeNode=tempTree;
       mirrorTree=pNode;
    }
    if(pNode->m_leftTreeNode)
        mirrorTree->m_leftTreeNode= mirrorRecursively(pNode->m_leftTreeNode);
    if(pNode->m_rightTreeNode)
        mirrorTree->m_rightTreeNode= mirrorRecursively(pNode->m_rightTreeNode);

    return mirrorTree;
}