2255:Tree Recovery

keyword

2分木　C++

概要

ノード数26以下の2分木がある。(root, left subtree, right subtree)、(left subtree, root, right subtree)の順にノードを出力した文字列がそれぞれ与えられるので、(left subtree, right subtree, root)の順にノードを出力する問題。
ノード数が小さいので、素直に各ノードに対して左の子と右の子を調べる。左の子はすぐに分かるが右の子はちょっと面倒。

int leftChild[30], rightChild[30];
char ans[30];
char preorder[30], inorder[30];
int pre[30], in[30];
int pos, n;

void dfs(int root){
    if(leftChild[root]<30) dfs(leftChild[root]);
    if(rightChild[root]<30) dfs(rightChild[root]);
    ans[pos++] = (char)(root + 'A');
    return ;
}

void dfs2(int root, int begin, int end){
    int left = leftChild[root], right;
    if(left < 30){
        dfs2(left, begin, in[root]);
    }
    if(in[root]<end-1){
        if(left==30){
            right = preorder[pre[root]+1];
        }
        else{
            for(right=preorder[pre[root]+1];
            (in[right]<in[root] || in[right]>=end);
            right = preorder[pre[right]+1]);
        }
        rightChild[root] = right;
        dfs2(right, in[root]+1, end);
    }
    return ;
}

int main(){
    int i, j;

    while(scanf("%s %s\n", preorder, inorder)!=EOF){
        REP(i,26) leftChild[i] = rightChild[i] = pre[i] = in[i] = 30;

        n = strlen(preorder);

        REP(i,n)preorder[i] -= 'A';
        REP(i,n)inorder[i] -= 'A';
        REP(i,n) pre[preorder[i]] = i;
        REP(i,n) in[inorder[i]] = i;


        REP(i,26)if(pre[i]<30)REP(j,26)if(i!=j && pre[j]<30){
            if(pre[i] + 1 == pre[j] && in[i] > in[j]) leftChild[i] = j;
        }

        dfs2(preorder[0], 0, n);

        pos = 0;
        dfs(preorder[0]);
        ans[pos] = '\0';

        printf("%s\n",ans);
    }

    return 0;
}