已知二叉树前序遍历和后序遍历,判断树是否唯一 - dblank

已知二叉树前序遍历和后序遍历,判断树是否唯一

我们都知道前序遍历的第一个序号是树的根节点,后序遍历的最后一个是树的根节点,则有这样的性质,前序遍历的第二序号是在后序遍历中是子树的最后一个节点,这样可以把前序遍历和后序遍历分为左右两个子树。同理后序的倒数第二个序号在前序遍历中也是子树的最后一个序号。根据这两个,我们可以求出两个中序遍历,如果一样则为一,否则不唯一。

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
const int N = 2000+ 10, Mod = 998244353, inf = 0x3f3f3f3f;
vector<int> pos, pre, ind1, ind2;
int n;
void build1(int pre_l,int pre_r,int pos_l, int pos_r)
{
    int id;
    for(int i = pos_l; i<=pos_r; i++)
    {
        if(pos[i] == pre[pre_l + 1])
            id = i;
    }
    if(id-pos_l>0)
        build1(pre_l+1, pre_l+id-pos_l+1, pos_l ,id);
    else if(id == pos_l) ind1.push_back(pos[id]);
    ind1.push_back(pre[pre_l]);
    if(pos_r-2-id>0)
        build1(pre_l+2+id-pos_l, pre_r, id+1, pos_r-1);
    else if(pos_r == id+2)ind1.push_back(pos[id+1]);
}
void build2(int pre_l,int pre_r,int pos_l, int pos_r)
{
    int id;
    for(int i = pre_l; i<=pre_r; i++)
    {
        if(pre[i] == pos[pos_r-1])
            id = i;
    }
    if(id-2-pre_l==0)
        ind2.push_back(pre[pre_l+1]);
    else if(id-2-pre_l>0)
        build2(pre_l+1, id-1,pos_l,pos_r-pre_r+id-2);

    ind2.push_back(pre[pre_l]);
    if(pre_r-id>0)
        build2(id, pre_r,pos_r-pre_r+id-1,pos_r-1);
    else if(pre_r==id)ind2.push_back(pre[id]);
}
int main()
{
    int  x;
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        cin>>x;
        pre.push_back(x);
    }
    for(int i = 0; i<n; i++)
    {
        cin>>x;
        pos.push_back(x);
    }
    ind1.clear();
    build1(0, n-1, 0, n-1);
    ind2.clear();
    build2(0, n-1, 0, n-1);
    int ok = 1;
    if(ind2!=ind1)ok=0;
    if(ok)puts("Yes");
    else puts("No");
    for(int i = 0; i<n-1; i++)
        cout<<ind1[i]<<" ";
    cout<<ind1[n-1]<<endl;
    return 0;
}

发表新评论