前序中序求后序的java算法是怎样的

前序中序求后序的java算法是怎样的，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
变量条件：二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
运行时限：1秒/测试数据。
输入格式：两行，第一行为前序遍历，第二行为中序遍历。
输出格式：若不能根据前序和中序遍历求出后序遍历，输出NO ANSWER；否则输出一行，为后序遍历。

/**
 * 前序遍历:GDAFEMHZ
 * 中序遍历:ADEFGHMZ
 *
 *
 * 两个步骤:
  根据前序中序,构造二叉树
  后序遍历二叉树

 * 根据前序遍历的特点得知,根结点为G
 * 根结点将中序遍历结果ADEFGHMZ分成ADEF和HMZ两个左子树、右子树。
 * 递归确定中序遍历序列ADEF和前序遍历序列DAFE的子树结构;
 * 递归确定中序遍历序列HMZ和前序遍历序列MHZ的子树结构;
 */
public class PostOrder{
    public static void main(String[] args) throws Exception{
//        Scanner in = new Scanner(System.in);
//        String pre,mid;
//        while(in.hasNext()){
//            pre = in.next();
//            mid = in.next();
//            System.out.println(postOrder(pre,mid));
//        }
        String pre = "ABDGCEFH";
        String mid = "DGBAECHF";
        System.out.println(postOrder(pre,mid));
    }
    private static String postOrder(String pre, String mid) throws Exception{
        if(pre.length() == 1)
            return pre;
        else if(pre.length() == 0)
            return "";
        int m = mid.indexOf(pre.charAt(0));
        return postOrder(pre.substring(1,m+1 ),mid.substring(0, m)) 
+ postOrder(pre.substring(m+1),mid.substring(m+1)) 
+ pre.charAt(0);
    }
}

/**
 * 中序遍历:ADEFGHMZ
 * 后序遍历:AEFDHZMG
 *
 *
 * 后序遍历最后一个结点即为根结点,即 根结点为G
 */
public class PreOrder {
    public static void main(String[] args) throws Exception{
        String post = "AEFDHZMG";
        String mid = "ADEFGHMZ";
        System.out.println(preOrder(post,mid));
    }
    private static String preOrder(String post, String mid) throws Exception{
        if(post.length() == 1)
            return post;
        else if(post.length() == 0)
            return "";
        int m = mid.indexOf(post.charAt(post.length() - 1));
        return post.charAt(post.length() - 1) 
+ preOrder(post.substring(post.length() - mid.length(),m),mid.substring(0,m)) 
+ preOrder(post.substring(m,post.length() - 1),mid.substring(m+1));
    }

}

看完上述内容，你们掌握前序中序求后序的java算法是怎样的的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！