L2-011. 玩转二叉树（不建树）

L2-011. 玩转二叉树

 

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

输入格式：

输入第一行给出一个正整数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<cstring>
#include<climits>
#include<queue>
#include<iostream>
using namespace std;
int a[1005], b[1005];
struct Node{
    int id;
    int c;
    int quan;
    bool operator <(const Node &a)const{
        if (a.c == c)return a.quan>quan;
        else return a.c < c;
    }
};
priority_queue<Node>que;
void Creat(int s, int e, int c)
{
    if (s>e)return;
    if (s == e){
        Node node;
        node.id = a[s];
        node.c = c;
        node.quan = s;
        que.push(node);
    }
    else{
        int p = s, min = b[a[p]];
        for (int i = s + 1; i <= e; i++){
            if (b[a[i]] < min){
                min = b[a[i]];
                p = i;
            }
        }
        Node node;
        node.id = a[p];
        node.c = c;
        node.quan = p;
        que.push(node);
        Creat(s, p - 1, c + 1);
        Creat(p + 1, e, c + 1);
    }
}
int main()
{
    
    int n; cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        int num; cin >> num;
        b[num] = i;
    }
    Creat(0, n - 1, 0);
    int flag = 0;
    while (!que.empty()){
        if (flag == 0){
            cout << que.top().id;
            flag++;
        }
        else{
            cout << " " << que.top().id;
        }
        que.pop();
    }
    cout << endl;
    return 0;
}