魔乐社区

1、题目：

2、代码：

#include<iostream>
#include<algorithm>
using namespace std;
struct Node
{
    int left;
    int right;
    int father;
    int ord;
} node[100010];
void preOrder(int m)
{
    if(m!=-1)
    {
        cout<<m<<" ";
        preOrder(node[m].left);
        preOrder(node[m].right);
    }
}

void posOrder(int m)
{
    if(m!=-1)
    {
        posOrder(node[m].left);
        posOrder(node[m].right);
        cout<<m<<" ";
    }
}
int main()
{
    int n;
    cin>>n;
    int i;
    for(i=1; i<=n; i++)
    {
        cin>>node[i].father;
    }
    for(i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        node[x].ord=i;
    }
    for(i=1; i<=n; i++)
    {
        node[i].left=-1;
        node[i].right=-1;
    }
    //为每个结点设置儿子 
    for(i=1; i<=n; i++)
    {
        if(node[node[i].father].left==-1)
        {
            node[node[i].father].left=i;
        }
        else
        {
            node[node[i].father].right=i;
        }
    }
    //确认左右子树,调整左右儿子位置 
    for(i=1; i<=n; i++)
    {
        if(node[i].left!=-1&&node[node[i].left].ord>node[i].ord)//如果左儿子在中序中的位置大于父亲在中序的位置，
        //说明这个应该是右儿子 
        {
            swap(node[i].left,node[i].right);
        }
        if(node[i].right!=-1&&node[node[i].right].ord<node[i].ord)//如果右儿子在中序中的位置小于父亲在中序的位置，
        //说明这个应该是左儿子
        {
            swap(node[i].left,node[i].right);
        }
    }
    preOrder(1);
    cout<<endl;
    posOrder(1);
    cout<<endl;
    return 0;
}