给定一个二叉树的前序遍历和中序遍历的序列，输出对应这个二叉树的后续遍历序列。

输入描述:

输入为一行。两个字符串,分别表示二叉树的前序遍历和中序遍历结果,用空格分隔。保证数据合法

输出描述:

对应输出后序遍历序列

示例1

输入

ABDEC DBEAC

输出

DEBCA 思路：先根据先序、中序序列建立二叉树，然后后序遍历

import java.util.Scanner; import javax.print.attribute.standard.PresentationDirection;  class TreeNode {     char val;     TreeNode left;     TreeNode right;     TreeNode(char x) { val = x; } }  public class Main {    public static  String preStr;    public static String midStr;         public static void main(String[] args) {        // TODO Auto-generated method stub        Scanner sc = new Scanner(System.in);        String s = sc.nextLine();        int pos = s.indexOf(" ");        preStr = s.substring(0,pos);        midStr = s.substring(pos+1,s.length());        //System.out.println("pre:"+preStr);        //System.out.println("midS:"+midStr);        TreeNode rs = creat(preStr,0,preStr.length()-1,midStr,0,midStr.length()-1);        rView(rs);    }    public static void rView(TreeNode root){        if(root!=null){            rView(root.left);            rView(root.right);            System.out.print(root.val);        }    }    public static TreeNode creat(String preStr,int pstart,int pend,String midStr,int mstart,int mend){        if(mstart>mend||pstart>pend) return null;        char[] cmidStr= midStr.toCharArray();        char[] cpreStr=preStr.toCharArray();        TreeNode root = new TreeNode(cpreStr[pstart]);        for(int i = mstart;i<=mend;i++)            if(cmidStr[i]==cpreStr[pstart]){                int len = i-mstart;                                 root.left = creat(preStr,pstart+1,pstart+len,midStr,mstart,i-1);                root.right = creat(preStr,pstart+len+1,pend,midStr,i+1,mend);            }            return root;       } }