给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8） 输入格式： 2 行字符串，均为大写字母组成，分别表示一棵二叉树的中序与后序排列。 输出格式： 1 行字符串，表示一棵二叉树的先序排列。 样例输入： BADC BDCA 样例输出： ABCD

根据中序和后序排列，我们可以得到二叉树的根节点，以及左子树和右子树的中序排列和后序排列。根据后序排列可以确定根节点，根据中序排列可以确定左子树和右子树的大小。因此我们可以递归地求解左子树和右子树，进而得到整棵二叉树的先序排列。

具体来说，假设当前二叉树的中序排列为 $A_1A_2\cdots A_n$，后序排列为 $B_1B_2\cdots B_n$，我们可以按照下面的步骤求出先序排列：

1. 如果中序排列为空，返回空字符串。
2. 否则，取出后序排列中最后一个元素 $B_n$ 作为根节点，在中序排列中找到根节点的位置 $k$，则左子树的中序排列为 $A_1A_2\cdots A_{k-1}$，右子树的中序排列为 $A_{k+1}A_{k+2}\cdots A_n$。
3. 由于后序排列中最后一个元素是根节点，因此后序排列中除去最后一个元素外，剩余的元素可以分为两部分，前一部分是左子树的后序排列，后一部分是右子树的后序排列。左子树的后序排列的长度为 $k-1$，右子树的后序排列的长度为 $n-k$。
4. 对左子树和右子树递归地求解先序排列，然后将根节点的值与左子树的先序排列和右子树的先序排列拼接起来，得到整棵二叉树的先序排列。

下面是完整的代码实现：

def get_preorder(inorder, postorder):
    if not inorder:
        return ''
    root = postorder[-1]
    k = inorder.index(root)
    left_inorder, right_inorder = inorder[:k], inorder[k+1:]
    left_postorder, right_postorder = postorder[:k], postorder[k:-1]
    left_preorder = get_preorder(left_inorder, left_postorder)
    right_preorder = get_preorder(right_inorder, right_postorder)
    return root + left_preorder + right_preorder

该算法的时间复杂度为 $O(n^2)$，其中 $n$ 是二叉树的节点数。由于每次都要在中序排列中查找根节点的位置，因此总共需要进行 $n$ 次查询。如果使用哈希表等数据结构，可以将查询的时间复杂度降为 $O(1)$，从而提高算法的效率。