pat学习 1527 https://www.acwing.com/problem/content/1529/

由于这题节点值可能重复（第一个例子里面 的8），所以l,r要存节点的下标而不是值，同样build返回的也是root的下标而不是值

没有镜像的时候（中序是从小到大）两个相同元素要选左边（距离较小的一边）的那个作为根节点（题目说了右边的元素大于等于左边元素，所以相同的要放右边)

镜像之后（中序是从大到小）两个相同的元素要选右边那个（距离较小的一边）的那个作为根节点，因为镜像之后，之前在右边的那一部分跑到左边了，也就是可以取到等号的情况在左边，所以相同的值时根是偏右边那个，子是偏左边那个。

注意求镜像的时候要清空l和r，不然两个家族的children搞不清了

输出后序遍历就是常规的方法

找中序中的root的下标(代码中用idx表示)由于是在区间il到ir找，所以可能会找不到，返回INF，表示建树失败了

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

const int N =1005, INF = 0x3f3f3f3f;

int pre[N], inter[N];

bool cmp(int a, int b)
{
    return a > b;
}

map<int, int> l, r;

int n;

//前序， 中序
int build1(int il, int ir, int pl, int pr)
{
    int rootIdx = pl;
    int idx = INF;
    for(int i = il; i <= ir; ++ i)
    {
        if(inter[i] == pre[rootIdx])    
        {
            idx = i;
            break;
        }
    }
    if(idx == INF)  return INF; //构建失败
    int llen = idx - il, rlen = ir - idx;
    if(llen > 0)//左子树
    {
        int rootIdx1 = build1(il, idx-1, pl+1, pl+llen);
        if(rootIdx1 == INF)    return INF; //构建失败
        l[rootIdx] = rootIdx1;
    }
    if(rlen > 0)//右子树
    {
        int rootIdx2 = build1(idx+1, ir, pl+llen+1, pr);
        if(rootIdx2 == INF)    return INF; //构建失败
        r[rootIdx] = rootIdx2; 
    }
    return rootIdx;
}

//镜像下的：前序， 中序
//此时中序改变
int build2(int il, int ir, int pl, int pr)
{
    int rootIdx = pl;
    int idx = INF;
    //一定要逆序，因为镜像之后，相同的元素选右边的那个作为根节点
    for(int i = ir; i >= il; -- i)
    {
        if(inter[i] == pre[rootIdx])    
        {
            idx = i;
            break;
        }
    }
    if(idx == INF)  return INF; //构建失败
    int llen = idx - il, rlen = ir - idx;
    if(llen > 0)//左子树
    {
        int rootIdx1 = build2(il, idx-1, pl+1, pl+llen);
        if(rootIdx1 == INF)    return INF; //构建失败
        l[rootIdx] = rootIdx1;
    }
    if(rlen > 0)//右子树
    {
        int rootIdx2 = build2(idx+1, ir, pl+llen+1, pr);
        if(rootIdx2 == INF)    return INF; //构建失败
        r[rootIdx] = rootIdx2; 
    }
    return rootIdx;
}

int cnt = 0; //防止末尾有空格的，糟糕的pat机制

void dfs(int uIdx)
{
    if(l.count(uIdx))  dfs(l[uIdx]);

    if(r.count(uIdx))  dfs(r[uIdx]);
    cnt ++;
    if(cnt == 1)    cout << pre[uIdx]; //第一次输出，不要前置空格
    else cout << " " << pre[uIdx];

}


int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
    {
        cin >> pre[i];
        inter[i] = pre[i];
    }
    sort(inter, inter+n);
    int rootIdx1 = build1(0, n-1, 0, n-1);

    if(rootIdx1 != INF)
    {
        cout << "YES" << endl;
        dfs(rootIdx1);
        return 0;
    }else
    {
        l.clear(), r.clear();
        sort(inter, inter+n, cmp);
        int rootIdx2 = build2(0, n-1, 0, n-1);
        if(rootIdx2 != INF)
        {
            cout << "YES" << endl;
            dfs(rootIdx2);
            return 0;
        }
        else
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    return 0;
}