参考

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

输入格式：
$输入第一行给出一个正整数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 <bits/stdc++.h>

using namespace std;

const int N = 40;

int in[N], pre[N], n;

struct node{
    int data;
    int l, r;
}tr[N];

int build_tr(int al,int ar,int bl,int br)
{
    if(al > ar || bl > br) return 0;
    int root = pre[al];
    int k = 0;
    while(root != in[k]) k ++;//中序遍历中找到根节点的位置 
    int len = k - bl;//将左子树的长度算出 递归用

    tr[root].data = root;


/*前序序列第一个元素作为根节点 所以左子树递归时前序序列的区间是[al+1, al+len] 中序遍历的区间[bl,bl+len-1]
    右子树递归时前序区间[al+len+1,ar] 中序区间是[bl+len+1,br]          */
    tr[root].l = build_tr(al+1,al+len,bl,bl+len-1);
    tr[root].r = build_tr(al+len+1,ar,bl+len+1,br);

    return root;
}



int main()
{
    cin >> n;
    for(int i=0;i<n;i++) cin >> in[i];
    for(int i=0;i<n;i++) cin >> pre[i];

    int root = build_tr(0,n-1,0,n-1);

    queue<node> q;
    q.push(tr[root]);
    bool flag = 1;

    while(q.size())
    {
        node t = q.front();
        q.pop();
        if(flag)
        {
            cout << t.data;
            flag = 0;
        }
        else cout << " " << t.data;

        //因为是镜像遍历 所以层序遍历的时候先右子树即可

        if(t.r) q.push(tr[t.r]);
        if(t.l) q.push(tr[t.l]);
    }
    return 0;
}

$同样的 L2-006 也可以用这种方式建树$
$给出后序遍历和中序遍历$

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

struct node{
    int data;
    int l, r;
}tr[N];

int in[N], after[N];
int n;

int build_tr(int al,int ar,int bl,int br)
{
    if(al > ar || bl > br) return 0;

    int root = after[ar];
    int k = 0;
    while(root != in[k]) k ++;
    int len = k - bl;

    tr[root].data = root;

    tr[root].l = build_tr(al,al+len-1,bl,bl+len-1);
    tr[root].r = build_tr(al+len,ar-1,bl+len+1,br);
    return root;
}



int main()
{
    cin >> n;

    for(int i=0;i<n;i++) cin >> after[i];
    for(int i=0;i<n;i++) cin >> in[i];

    int root = build_tr(0,n-1,0,n-1);

    queue<node> q;
    q.push(tr[root]);
    bool st = 1;


    while(q.size())
    {
        node t = q.front();
        q.pop();

        if(st)
        {
            cout << t.data;
            st = 0;
        }
        else cout << " " << t.data;

        if(t.l) q.push(tr[t.l]);
        if(t.r) q.push(tr[t.r]);
    }

    return 0;
}