剑指offer - 二叉树的镜像

题目

请完成一个函数，输入一棵二叉树，该函数输出它的镜像。

二叉树结点的定义：

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》