acwing1259. 二叉树遍历（层序中序重构二叉树）

树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。
假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。

输入格式

两行，每行是由大写字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。

输出格式

一行，表示二叉树的先序序列。

数据范围

输入字符串的长度均不超过26。

输入样例：

DBEAC ABCDE

输出样例：

ABDEC

import java.io.*;
import java.util.*;
public class Main {
    static class TreeNode {
        char val;
        TreeNode left, right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String inorder, lorder;
        inorder = cin.readLine();
        lorder = cin.readLine();
        int n = inorder.length();
        // 存中序字母及它的下标
        Map<Character, Integer> map = new HashMap<>();
        TreeNode[] q = new TreeNode[30];
        boolean[] st = new boolean[n + 1];
        for (int i = 0; i < n; ++i) map.put(inorder.charAt(i), i);
        q[0] = new TreeNode(lorder.charAt(0));
        // 按层遍历 i是当前层起点，j是下一层起点
        for (int i = 0, j = 1; i < n; ) {
            for (int end = j; i < end; ++i) {   //遍历当前层
                int pos = map.get(lorder.charAt(i));   //当前节点的中序位置
                st[pos] = true;
                // 判断左儿子是否存在
                if (pos > 0 && !st[pos - 1]) {
                    q[i].left = new TreeNode(lorder.charAt(j));
                    q[j ++] = q[i].left;
                }
                // 判断右儿子是否存在
                if (pos + 1 < n && !st[pos + 1]) {
                    q[i].right = new TreeNode(lorder.charAt(j));
                    q[j ++] = q[i].right;
                }
            }
        }
        dfs(q[0]);
    }
    static void dfs(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}