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

二叉树的镜像

2024-07-07 18:57:22   225人阅读

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

分析：何为镜像？

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


联系
我们