[POJ] 2255 Tree Recovery.cpp

#include <cstdio>
#include <cstring>
using namespace std;

char Preorder[30], Inorder[30];

void Postorder(int PL, int PR, int IL, int IR);
int FindInorderRoot(char c, int L, int R);

int main()
{
    while (scanf("%s %s", Preorder, Inorder) == 2) {
        Postorder(0, strlen(Preorder)-1, 0, strlen(Inorder)-1);
        putchar('\n');
    }
    return 0;
}
void Postorder(int PL, int PR, int IL, int IR) // PL, PR: Preorder的左右界 IL, IR: Inorder的左右界
{
    if (PL == PR) {  // 左界等於右界,
        printf("%c", Preorder[PL]);
        return;
    }
    // P_root, I_root: 目前這個Tree的root的index
    int P_root = PL;
    int I_root = FindInorderRoot(Preorder[P_root], IL, IR);

    // 要分成左右子樹, P_Lsub_L, P_Lsub_R: 為左子樹在Preorder的左右界,反之另外兩個為右子樹左右界
    int P_Lsub_L, P_Lsub_R, P_Rsub_L, P_Rsub_R;

    // I_Lsub_L, I_Lsub_R: 為左子樹在Inorder的左右界,另外兩個為右子樹的左右界
    int I_Lsub_L, I_Lsub_R, I_Rsub_L, I_Rsub_R;

    bool hasLsub = 1, hasRsub = 1;  //確認左右子樹是否存在

    I_Lsub_L = IL;
    I_Lsub_R = I_root - 1;
    if (I_Lsub_L > I_Lsub_R) hasLsub = 0;

    I_Rsub_L = I_root + 1;
    I_Rsub_R = IR;
    if (I_Rsub_L > I_Rsub_R) hasRsub = 0;

    if (hasLsub) {
        P_Lsub_L = P_root + 1;
        P_Lsub_R = P_Lsub_L + (I_Lsub_R - I_Lsub_L);
    }
    if (hasRsub) {
        P_Rsub_L = (hasLsub) ? P_Lsub_R + 1 : P_root + 1;
        P_Rsub_R = PR;
    }

    //若左(右)子樹存在,則繼續遞迴分割,直到元素剩下一個
    //底下三行code的順序為Postorder(Left, Right, Root)
    if (hasLsub) Postorder(P_Lsub_L, P_Lsub_R, I_Lsub_L, I_Lsub_R);
    if (hasRsub) Postorder(P_Rsub_L, P_Rsub_R, I_Rsub_L, I_Rsub_R);
    printf("%c", Preorder[P_root]);
}
int FindInorderRoot(char c, int L, int R)
{
    while (Inorder[L] != c && L <= R) L++;
    return L;
}