二叉树遍历 内存限制：256 MB 时间限制：1.000 S 评测方式：文本比较 命题人：外部导入 提交：1 解决：1 题目描述 树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。 假定一棵二叉树一个结点用一个字符描述，现在给出中序和后序遍历的字符串，求该树的先序遍历字符串。 输入 两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和后序遍历的序列。 输出 一行，表示二叉树的先序序列。 样例输入 复制 DBEAC ABCDE 样例输出 复制 ABDEC

以下是一种基于递归的实现方式，可以用来解决该问题：

def build_tree(inorder, postorder):
    if not inorder or not postorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    root_idx = inorder.index(root_val)
    left_inorder = inorder[:root_idx]
    right_inorder = inorder[root_idx+1:]
    left_postorder = postorder[:root_idx]
    right_postorder = postorder[root_idx:-1]
    root.left = build_tree(left_inorder, left_postorder)
    root.right = build_tree(right_inorder, right_postorder)
    return root

def preorder_traversal(root):
    if not root:
        return []
    res = [root.val]
    res += preorder_traversal(root.left)
    res += preorder_traversal(root.right)
    return res

inorder = input().strip()
postorder = input().strip()
root = build_tree(inorder, postorder)
preorder = preorder_traversal(root)
print("".join(preorder))

该算法的时间复杂度为 $O(n^2)$，其中 $n$ 是二叉树的节点数。可以通过使用哈希表来优化查找节点位置的时间复杂度，将其优化到 $O(n)$。