一 问题描述

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

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

二 输入和输出

1 输入

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

2 输出

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

3 输入样例

DBACEGF ABCDEFG

4 输出样例

ACBFGED

三 算法设计

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

四 实现

package tree;

import java.util.Scanner;

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

    /**
     * 功能描述：后序遍历,并打印后序遍历序列
     *
     * @param l1：二叉树先序遍历的树根位置
     * @param l2：二叉树中序遍历的树根位置
     * @param n：树的节点个数
     * @author cakin
     * @date 2022/6/13
     */
    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);
    }
}

五 测试

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