树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种 遍历的序列就可以确定一棵二叉树的结构。 假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树 的先序遍历字符串。 输入 共两行，每行是由字母组成的字符串（一行的每个字符都是唯一的）， 分别表示二叉树的中序遍历和按层遍历的序列 例如：DBEAC ABCDE 。 输出 一行，表示二叉树的先序序列。 例如：ABDEC。 用c++实现

以下是用C++实现的代码：

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

// 定义二叉树结点结构体
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};

// 根据中序遍历和按层遍历构建二叉树
TreeNode* buildTree(string inorder, string levelorder) {
    if (inorder.empty() || levelorder.empty()) return nullptr;
    unordered_map<char, int> inMap; // 存储中序遍历中每个字符的位置
    for (int i = 0; i < inorder.size(); ++i) {
        inMap[inorder[i]] = i;
    }
    TreeNode* root = new TreeNode(levelorder[0]); // 根结点是按层遍历的第一个字符
    queue<TreeNode*> q;
    q.push(root);
    for (int i = 1; i < levelorder.size(); ++i) {
        char c = levelorder[i];
        TreeNode* node = new TreeNode(c);
        if (inMap[c] < inMap[q.front()->val]) { // 在左子树中
            q.front()->left = node;
        } else { // 在右子树中
            while (!q.empty() && inMap[c] > inMap[q.front()->val]) {
                // 找到当前结点的父结点
                q.front()->right = node;
                q.pop();
            }
        }
        q.push(node);
    }
    return root;
}

// 先序遍历二叉树
void preorder(TreeNode* root) {
    if (root) {
        cout << root->val;
        preorder(root->left);
        preorder(root->right);
    }
}

int main() {
    string inorder, levelorder;
    cin >> inorder >> levelorder;
    TreeNode* root = buildTree(inorder, levelorder);
    preorder(root);
    return 0;
}

该算法的时间复杂度为 $O(n)$，其中 $n$ 是二叉树中结点的个数。该算法利用了中序遍历和按层遍历的性质，可以有效地构建二叉树，并输出它的先序遍历序列。