【解题】输出给定二叉树的镜像（C++实现）

题目描述

完成一个函数，输入一个二叉树，输出这个二叉树的镜像。二叉树的节点如下定义：

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);
    }
}