输入一颗二元查找树，将该树转换为它的镜像

时间：2017-12-06 00:24:58 收藏：0 阅读：279

输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

例如给定下列的输入：

技术分享图片

然后有如下的输出：

技术分享图片

解法一：递归

首先交换根节点8的左右子树，10，6的左右子树顺序不变，然后交换根节点6的左右子节点，直到左右子节点为空为止。

代码：

BSTreeNode*digui(BSTreeNode*pRoot)
{
    if(pRoot!=NULL)
    {
        BSTreeNode * pRight=pRoot->right;
        BSTreeNode * pLeft=pRoot->left;
               //递归
        pRoot->left=digui(pRight);//右子树转换成左子树
        pRoot->right=digui(pLeft);//左子树转换右子树
    }
    return pRoot;
}

解法二：循环

我们需要一个辅助栈

每次取栈顶元素交换左右子女，然后将左右子女分别压入辅助栈，当栈中元素为空时，结束循环。

应用栈的原理，首先把8压栈。然后开始操作栈，如果栈不空，就弹出栈中的元素，并交换元素的左右两个子节点。

如果这两个节点分别处理，如果不空，然后压入栈中，压栈操作完后，再对栈进行操作。

（本质也是递归）

代码如下：

BSTreeNode*xunhuan(BSTreeNode*pRoot)
{
    if(pRoot!=NULL)
    {
        stack<BSTreeNode *> stk;//辅助栈
        stk.push(pRoot);//压入根节点
        while(stk.size())
        {
            BSTreeNode*pNode=stk.top();
             BSTreeNode *pLeft = pNode->left;  
            BSTreeNode* pRight = pNode->right;  
            stk.pop();  
  
            if(pLeft != NULL)  
                stk.push(pLeft);  
            if(pRight != NULL)  
                stk.push(pRight);  
            pNode->left = pRight;  //交换左右子女  
            pNode->right = pLeft;  
        }  
    }  
    return pRoot;  
}

原文：http://www.cnblogs.com/cdsn/p/7990195.html