1. 已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。

根据二叉树的前序遍历和中序遍历可以确定二叉树的结构，进而确定其后序遍历。根据前序序列可知B是该二叉树的根节点，根据中序序列可知，B的左子树的中序序列为FEG，右子树的中序序列为CHD。由此可以得到左子树的前序序列为EF和中序序列为FEG，右子树的前序序列为CG和中序序列为CHD。因此，左子树的后序序列为EGF，右子树的后序序列为CDH，根节点B的后序序列为GFEDHCB。所以，该二叉树的后序序列为GFEDHCB。

相关问题

已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是

根据二叉树的前序遍历和中序遍历可以确定该二叉树的结构，具体步骤如下：

1. 前序遍历的第一个节点是根节点，即B是该二叉树的根节点；
2. 在中序遍历中，找到根节点B所在的位置，位于中间，左边是该二叉树的左子树，右边是该二叉树的右子树；
3. 根据左子树的长度，在前序遍历中找到左子树的前序遍历序列，即EF，右子树的前序遍历序列为CGDH；
4. 根据左子树和右子树的前序遍历序列，在中序遍历中分别找到左子树和右子树的中序遍历序列，左子树的中序遍历序列为FEBG，右子树的中序遍历序列为CHD；
5. 重复1~4步骤，递归构造左子树和右子树。

根据上述步骤可得，该二叉树的后序遍历序列为：FEGCHDB。

证明:已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树

要证明已知一棵二叉树的前序序列 (Preorder) 和中序序列 (Inorder) 可以唯一确定该二叉树，我们可以采用分步分析法。

**步骤1：前序序列中的根节点**
前序序列的第一个元素通常是根节点，因为它先访问根再遍历左子树和右子树。因此，通过前序序列，我们可以直接找到根节点。

**步骤2：寻找根节点在中序序列中的位置**
在中序序列中，由于左子树会先于根节点被访问，所以我们可以从中序序列的一开始查找第一个大于根节点的元素，这个元素的位置就是根节点的左子树在中序序列中的结束位置。

**步骤3：划分左右子树**
接着，我们用找到的位置将中序序列分为两部分：左边的部分包含左子树的所有节点，右边的部分则包含根节点和右子树。因为中序序列是递增的，所以这部分很容易确定。

**步骤4：递归构建子树**
现在我们可以对左右子树分别进行同样的操作，即找出它们的前序和中序序列。根据这两个序列，可以继续划分出每个子树的结构，直到所有子树都被构建出来。

**结论：唯一性**
由于前序和中序序列包含了关于节点访问顺序的完整信息，而且按照特定规则一步步地重建了整个树的过程是唯一的，所以给定一棵二叉树的前序和中序序列，能够唯一确定这棵树的结构。