Tree Recovery

Problem UVa: 536 - Tree Recovery

给了pre-order 和 in-order traversal 序列，要求输出post-order

The idea behind the code below is this:
1) The root is first element of the pre-order traversal
2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
3) The children of the current root are the first elements of the sub-pre-order-traversals.
4) recurse and put the numbers of the children in an array
5) recurse in post-order traversal through the new tree

/* 536 - Tree Recovery */
/* recursion */

#include <iostream>
char preorder[30];
char inorder[30];

void recover(int x1, int y1, int x2, int y2) {

    char t = preorder[x1];
    if(x1 == y1) {
        printf("%c", t);
        return;
    }  

    // locate the root position in in-order 
    // which split the travel seq into two halves
    int pos;
    for(int i = x2; i <= y2; ++i)
        if(inorder[i] == t) {
            pos = i;
            break;
        }

    int p = x1+pos-x2;

    // visit left sub-tree
    if(pos-1 >= x2)
        recover(x1+1, p , x2, pos-1);
    // visit right sub-tree
    if(y2 >= pos+1)
        recover(p+1, y1, pos+1, y2);

    // postorder -> print root at last
    printf("%c", t);
}
int main() {

    while(scanf("%s %s ",preorder, inorder) != EOF) {
        int L = strlen(preorder) - 1;
        recover(0, L, 0, L); // first <0,L> is preorder index, second <0,L> is in-order index
        printf("\n");
    }
}

Problem UVa: 10410 Tree Reconstruction

给了BFS和DFS traversal序列，要输出每个节点和它相应的叶子结点