1. 

package problemSetVolumes.volume005;

import java.util.Scanner;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 536 - Tree Recovery
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=477
*
* @author Siegfried Ippisch
* @version 1.0
*
* Method : -
* Status : Accepted
* Runtime: 0.116
*/
public class TreeRecovery {

static class Tree{

final char name;
final Tree left;
final Tree right;

// preorder traversal (root, left subtree, right subtree)
// inorder traversal (left subtree, root, right subtree)
Tree(String preorder, String inorder){
name = preorder.charAt(0);

// Substrings for left subtree
int lengthL = inorder.indexOf(name);
if(lengthL > 0){
String inorderLeft = inorder.substring(0,lengthL); // left from "name"
String preorderLeft = preorder.substring(1,lengthL+1); // same number of chars here
left = new Tree(preorderLeft, inorderLeft);
} else{
left = null;
}

// Substrings for right subtree
int lengthR = inorder.length() - inorder.indexOf(name) -1;
if(lengthR > 0){
String inorderRight = inorder.substring(lengthL+1); // right from "name"
String preorderRight = preorder.substring(lengthL+1); // same number of chars here
right = new Tree(preorderRight, inorderRight);
} else{
right = null;
}
}

// postorder traversal (left subtree, right subtree, root)
public String toString(){
return (left != null ? left.toString():"") +
(right != null ? right.toString():"") + name;
}
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);

while(in.hasNext()){
System.out.println(new Tree(in.next(), in.next()));
}

in.close();
}

}

2.

package acm_536_tree_recovery;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_536_tree_recovery
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=477
*
* @author Martin Lambeck
* @version 1.0, 10.08.2010
*
* Method : ad hoc
* Status : Accepted
* Runtime: 0.128
*/

import java.util.Scanner;

public class Main
{
static Scanner sc = new Scanner(System.in);

public static void main(String... args)
{
while (testcase());
}

public static boolean testcase()
{
if (!sc.hasNext())
return false;

String preord = sc.next();
String inord = sc.next();


Node top = recover(preord, inord);


StringBuilder str = new StringBuilder();

postorder(top, str); //generate output

System.out.println(str.toString());

return true;
}

static void postorder(Node pnode, StringBuilder str)
{
if (pnode.left != null)
postorder(pnode.left, str);

if (pnode.right != null)
postorder(pnode.right, str);

str.append(pnode.name);
}

public static Node recover(String preord, String inord)
{
if (preord.length() == 0)
return null;

Node pnode = new Node(preord.charAt(0)); //root is first char of preord

int ini = inord.indexOf("" + pnode.name); //position of root in inord

//new preord = middle part of old preord; new inord = left part of old inord
pnode.left = recover(preord.substring(1, ini + 1), inord.substring(0, ini));

//new preord = right part of old preord; new inord = right part of old inord
pnode.right = recover(preord.substring(1 + ini), inord.substring(ini + 1));

return pnode;
}

}

class Node
{
char name;
Node left = null;
Node right = null;

public Node(char nme)
{
name = nme;
}
}