玩转二叉树 PTA 逻辑训练

7-11 玩转二叉树 （25 分) 给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式： 输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式： 在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例： 7 1 2 3 4 5 6 7 4 1 3 2 6 5 7 输出样例： 4 6 1 7 5 3 2

呃，想清楚就好了

#include
using namespace std;
const int maxn = 31;
class T
{
public:
    int num;
    T* lc, * rc;
    T()
    {
        num = 0;
        lc = rc = NULL;
    }
};
int n;
int zhong[maxn], qian[maxn];
T* root;
queue q[2];
int pre = 0, nextt = 1;
void build(T &s, int zs, int ze, int qs, int qe)
{
    set se;
    int r = qian[qs];
    s.num = r;
    if (zs == ze)return;
    int lzs, lze, rzs, rze;
    int lqs, lqe, rqs, rqe;
    int zmid = zs;
    while (zhong[zmid] != r)
    {
        se.insert(zhong[zmid]);
        zmid++;
    }
    lzs = zs; lze = zmid - 1;
    rzs = zmid + 1; rze = ze;
    int qmid = qs + 1;
    bool flag = (se.find(qian[qmid]) != se.end());
    if (flag)
    {
        while ((se.find(qian[qmid]) != se.end()) == flag && qmid <= qe)qmid++;
        lqs = qs + 1; lqe = qmid - 1;
        rqs = qmid; rqe = qe;
    }
    else
    {
        lqs = qs + 1; lqe = qs;
        rqs = qs + 1; rqe = qe;
    }

    if (lze >= lzs && lqe >= lqs)
    {
        s.lc = new T();
        build(*s.lc, lzs, lze, lqs, lqe);
    }

    if (rze >= rzs && rqe >= rqs)
    {
        s.rc = new T();
        build(*s.rc, rzs, rze, rqs, rqe);
    }
}
void out()
{
    q[0].push(root);
    while (q[0].size() || q[1].size())
    {
        while (q[pre].size())
        {
            T* p = q[pre].front();
            q[pre].pop();
            if (p != root)printf(" ");
            printf("%d", p->num);
            if (p->rc != NULL)
            {
                q[nextt].push(p->rc);
            }
            if (p->lc != NULL)
            {
                q[nextt].push(p->lc);
            }
        }
        swap(pre, nextt);
    }
    printf("
");
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i != n; i++)
    {
        scanf("%d", &zhong[i]);
    }
    for (int i = 0; i != n; i++)
    {
        scanf("%d", &qian[i]);
    }
    root = new T();
    build(*root, 0, n - 1, 0, n - 1);
    out();
    return 0;
}