题目描述

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示前序遍历（父节点->左孩子->右孩子）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出后序遍历（左孩子->右孩子->父节点）的结果。

解答要求时间限制：1000ms, 内存限制：100MB

输入
每个输入文件包含两串字母，各占一行。（每串只包含大写字母）
第一行字母表示前序遍历结果，第二行字母表示中序遍历结果。

输出
输出仅一行，表示后序遍历的结果，结尾换行。

样例
输入样例 1
DBACEGF
ABCDEFG

输出样例 1
ACBFGED

提示样例 1
提示
前序遍历：根—>左孩子—>右孩子
中序遍历：左孩子—>根—>右孩子
后序遍历：左孩子—>右孩子—>根
所谓的前中后指的是根的位置，而左右孩子顺序是不变的。

例如已知前序遍历是DBACEGF，中序遍历是ABCDEFG，那么由前序遍历先根，可知道D是树的根，再看在中序遍历中D左边是ABC，所以可知道ABC一定在D的左子树上，而EFG在D的右子树上。
那么前序遍历为BAC,中序遍历为ABC，所以B为根，在中序遍历中A在B的左边，C在B的右边，所以A为B的左孩子，C为B的右孩子。

思路：先从先序遍历中找到根节点，然后从中序遍历中找到左子树和右子树，递归，构建二叉树，最后再进行后序遍历。

代码实现

import java.util.*;

public class Test {

    public static class Tree{
        private Tree left;
        private Tree right;
        private String value;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //前序遍历
        String pre = scanner.next();
        //中序遍历
        String in = scanner.next();

        Tree tree = buildTree(pre, in);

        List<String> list = new ArrayList<>();
        postOrder(tree, list);
        System.out.println(String.join("", list));
    }

    public static Tree buildTree(String pre, String in){
        if (pre.length() == 0){
            return null;
        }
        //从先序遍历中获取根节点，创建根节点
        String rootValue = pre.substring(0, 1);
        Tree root = new Tree();
        root.value = rootValue;
        int rootIndex = in.indexOf(rootValue);

        //获取左右子树
        String inLeft = in.substring(0, rootIndex);
        String inRight = in.substring(rootIndex + 1);
        String preLeft = pre.substring(1, rootIndex+1);
        String preRight = pre.substring(rootIndex+1);

        //递归创建左右子树
        root.left = buildTree(preLeft, inLeft);
        root.right = buildTree(preRight, inRight);
        return root;
    }

    //后续遍历
    public static void postOrder(Tree root,List<String> list){
        if (root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.value);
    }

}