软件大赛题目----（第十五个）二叉树

已知某二叉树的先序序列和中序序列，编程计算并输出该二叉树的后序序列。

输入说明：仅一组数据，分为两行输入，第一行表示指定二叉树的先序序列，第二行表示该二叉树的中序序列，序列

元素均为大写英文字符，表示二叉树的结点。

输出说明：在一行上输出该二叉树的后序序列。


输入样本：


ABDGCEFH


DGBAECHF


输出样本：

GDBEHFCA

package com.bird.exam;

import java.util.Scanner;

/**
 * 
 * @author Bird
 *已知某二叉树的先序序列和中序序列，编程计算并输出该二叉树的后序序列。
 *
	输入样本：

	ABDGCEFH

	DGBAECHF

	输出样本：

	GDBEHFCA
 */
public class Tree {
	
	private static char preoder[];
	private static char inoder[];
	
	public static void find(int preleft, int preright, int inleft, int inright){
		int i = 0, lsize=0,rsize=0;
		if(preleft<=preright && inleft<=inright){
			for(i=inleft; i<=inright; i++){
				if(preoder[preleft]==inoder[i])break;
			}
			
			lsize=i-inleft;
			rsize=inright-i;
			
			if(lsize>0)find(preleft+1,preleft+lsize,inleft,i-1);
			
			if(rsize>0)find(preleft+1+lsize,preright,i+1,inright);
			
			System.out.print(preoder[preleft]);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String pre=sc.next();
		String inorder=sc.next();
		preoder = pre.toCharArray();
		inoder = inorder.toCharArray();
		find(0,preoder.length-1,0,inorder.length()-1);
	}
}