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

二叉树的镜像

题目:请完成一个函数,输入二叉树,该函数输出他的镜像。二叉树的节点定义如下:

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

分析:我们先进行前序遍历这棵树上的结点,如果遍历到的结点有子节点,就交换他的两个子节点。当交换完所有非叶子节点的左右子节点之后,就得到了树的镜像。

实现如下:

void MirrorRecursively(BinaryTreeNode* pNode)
{
    if(pNode==NULL)
        return;
    if(pNode->m_pLeft==NULL&&pNode->m_pRight==NULL)
        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);
}


本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1584926

二叉树的镜像