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

根据扩展二叉树的定义，我们可以发现：

1. 先序遍历的第一个结点一定是根结点。
2. 对于一个非空结点，其后一个结点一定是其左子结点（如果有的话）或右子结点（如果没有左子结点）。
3. 对于一个空结点，其后一个结点一定是其父结点的右子结点（如果有的话）或者是其某个祖先结点的右子结点（如果没有父结点的右子结点）。

根据这些特点，我们可以先用先序序列构建出二叉树，然后再通过中序遍历和后序遍历的特点来求出中序和后序序列。

具体实现过程如下：

1. 用先序序列构建二叉树。具体实现可以使用递归，每次取出一个结点，如果是非空结点，则创建一个新结点，并将其作为当前结点的左子结点或右子结点，然后递归处理其左子树和右子树。如果是空结点，则直接返回空指针。
2. 中序遍历二叉树，得到中序序列。
3. 后序遍历二叉树，得到后序序列。

代码实现如下：

相关问题

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

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

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

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

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

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