100题_11 求二元查找树的镜像

时间：2011-03-07 来源：小橋流水

题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。例如输入：
8

/ \

6 10

/\ /\

5 7 9 11
输出：
8

/ \

10 6

/\ /\

11 9 7 5

这题相对很简单，没什么说的，直接代码了

核心代码 void BSTree::mirrorRec(BSTreeNode* node)
{
    if (!node)
        return;
    mirrorRec(node->lc);
    mirrorRec(node->rc);
    BSTreeNode* tmp = node->lc;
    node->lc = node->rc;
    node->rc = tmp;
}

void BSTree::mirrorRec() // 镜像递归
{
    mirrorRec(root);
}

void BSTree::mirror() // 非递归
{
    stack<BSTreeNode*> st;
    st.push(root);
    while (!st.empty())
    {
        BSTreeNode *t = st.top(), *tmp;
        st.pop();
        tmp = t->lc;
        t->lc = t->rc;
        t->rc = tmp;
        if (t->lc)
            st.push(t->lc);
        if (t->rc)
            st.push(t->rc);
    }
}

关于二叉查找树的定义可以参看100题_01

相关阅读更多 +