已知一棵二叉树中每个结点值为单个字符，其中序和后序序列分别为BFDJGACHKEI和FJGDBKHIECA，请画出该二叉树，并给出该二叉树的先序序列

根据中序和后序序列，可以重建该二叉树如下：

      I
     / \
    /   \
   H     E
  / \   / \
 /   \ /   \
B    D K    C
     / \     
    /   \    
   F     G   

该二叉树的先序序列为：`I H B D K F G E C A`

相关问题

题目描述 假设二叉树中每个结点值为单个字符(不超过100个)，已知其中序序列和后序序列，求二叉树的先序序列。 输入格式 两行，每行一个字符串，分别为二叉树的中序序列和后序序列 输出格式 一个字符串，为二叉树的先序序列

算法思路：

由于后序序列的最后一个元素为树的根节点，因此可以根据后序序列找到根节点，然后再根据中序序列，将树分为左右子树，递归求解即可。

具体来说，假设后序序列的最后一个元素为根节点 $root$，在中序序列中找到 $root$ 的位置 $pos$，则中序序列中 $pos$ 左边的元素为树的左子树，右边的元素为树的右子树。对于左子树和右子树，我们分别递归求解，得到左子树的先序序列 $pre_{left}$ 和右子树的先序序列 $pre_{right}$，然后将 $root$、$pre_{left}$ 以及 $pre_{right}$ 拼接在一起，构成整棵树的先序序列。

递归的结束条件是中序序列为空。

算法时间复杂度为 $O(n^2)$，其中 $n$ 为树的节点数。因为每次递归都需要在中序序列中找到根节点的位置，最坏情况下需要遍历整个中序序列，时间复杂度为 $O(n)$；而总共有 $n$ 个节点需要处理，因此总时间复杂度为 $O(n^2)$。

Python 代码：