POJ2255 java

先序遍历：根，左，右
中序遍历：左，右，根
后序遍历：左，右，根

每次我们只需要传入树mid中的开始位置，和结束为止
首先，先序遍历的第一个为根元素
我们只需要遍历pre数组中的字符
并找到此字符在mid数组中的对应位置，他就是此树对应的根元素
在mid中他的左边就是他的左子树，右边就是右子树
再分别对左 右子树按照刚才的方法递归
直到开始位置>结束位置说明没有左子树或者右子树了，就输出此结点

import java.util.Scanner;

public class Main2 {
    private static char[] pre;
    private static char[] mid;
    private static int p=-1;//pre数组的指针

    public static void main(String[] args) {
    	Scanner sc=new Scanner(System.in);
    	while(sc.hasNext()) {
    		pre=sc.next().toCharArray();
    		mid=sc.next().toCharArray();
    		tree(0,pre.length-1);
    		System.out.println();
    		p=-1;//指针置为-1
    	}
    }

	private static void tree(int start, int end) {
		if(start>end) {//没有左子树了  或  没有右子树了
			return;
		}
		p++;//首先指针+1
		for (int k = start; k <= end; k++) {//从树的开始位置到结束为止循环
			if(pre[p]==mid[k]) {//找到
				tree(start, k-1);//先输出看左子树
				tree(k+1, end);//再输出右子树
				System.out.print(mid[k]);//最后输出根元素
				break;
			}
		}
	}
}