由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

我们可以根据扩展二叉树的先序序列来还原二叉树，并且在还原的过程中得到其中序和后序序列。具体步骤如下：

1. 将扩展二叉树的先序序列存储为一个字符数组pre，其中pre[i]表示第i个结点的值（如果是空结点则为'·'）。

2. 定义一个指针idx，初始值为0，表示当前要还原的结点在pre中的下标。

3. 定义一个递归函数buildTree，该函数的参数为当前要还原的子树的根结点在pre中的下标范围[low, high]，返回值为还原出来的子树的根结点。

4. 在buildTree函数中，如果low > high，则返回空指针，表示当前子树为空。

5. 否则，取出pre[idx]的值，创建一个新的结点，并将idx加1。

6. 如果pre[idx]的值为'·'，则表示当前结点的左子树为空，否则递归调用buildTree函数构建左子树，其范围为[low+1, mid]，其中mid为当前结点的下标。

7. 同理，如果pre[idx]的值为'·'，则表示当前结点的右子树为空，否则递归调用buildTree函数构建右子树，其范围为[mid+1, high]。

8. 在buildTree函数的末尾，返回当前创建的结点，表示已经还原出了这个子树的根结点。

9. 最终，调用buildTree(0, n-1)来还原整棵二叉树，并得到其中序和后序序列。

下面是实现该算法的Python代码：

相关问题

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用'.'补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列

我可以帮你解决这道题目。对于原二叉树中的每个节点，我们可以通过以下方式将其编码到一个字符串中：如果该节点有左子树，则将其左子树的编码加入该节点的编码中；如果该节点有右子树，则将其右子树的编码加入该节点的编码中。最后，将所有节点的编码连接起来就得到了扩展二叉树的先序和后序序列。需要注意的是，这个编码方案可以保证通过先序和后序序列恢复出原二叉树。

给定二叉树的先序、中序和后序遍历序列中的任意两个，就可以唯一确定一棵二叉树。 ‏

这个说法是不正确的。虽然先序、中序和后序遍历序列可以唯一确定一棵二叉树，但是任意两个遍历序列并不能唯一确定一棵二叉树。这是因为存在多个不同的二叉树，它们的先序、中序和后序遍历序列相同。例如，以下两棵二叉树的先序、中序和后序遍历序列都是一样的：

    1                  2
   / \                / \
  2   3              1   4
     / \            / \
    4   5          3   5

因此，如果只给定先序、中序或后序中的任意两个遍历序列，就不能确定唯一的二叉树。