还原二叉树

小杰克喜欢玩二叉树。他最喜欢的游戏是根据二叉树节点的大写随机进行构造。

为了记录他的树，他为每颗树都写了两个字符串：一个先序遍历（根，左子树，右子树）和一个中序遍历（左子树、根、右子树）。上图所示的树，先序遍历是 DBACEFG，中序遍历是 ABCDEFG。他认为这样一对字符串可以提供足够的信息，以便重建这颗树。

输入包括两个字符串，表示二叉树的先序遍历和中序遍历。两个字符串都由唯一的大写字母组成。

输出该树的后序遍历序列（左子树、右子树、根）。

DBACEGF ABCDEFG

ACBFGED

本问题给出二叉树的先序和中序序列，要求输出后序序列。无须构建二叉树，只需在还原二叉树的同时，输出后序序列即可。根据先序序列找根，以中序序列划分左右子树。

package tree;


import java.util.Scanner;


public class UVA536 {
    // 先序序列
    private static String preorder;
    // 中序序列
    private static String inorder;


    
    static void postorder(int l1, int l2, int n) {
        if (n <= 0) {
            return;
        }
        // 在中序序列中找到根的位置
        int len = inorder.indexOf(preorder.charAt(l1)) - l2;
        postorder(l1 + 1, l2, len);
        postorder(l1 + 1 + len, l2 + len + 1, n - len - 1);
        System.out.print(preorder.charAt(l1));
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        preorder = scanner.nextLine();
        inorder = scanner.nextLine();
        int len = preorder.length();
        postorder(0, 0, len);
    }
}

绿色表示输入，白色表示输出