若一棵二叉树后序遍历和中序遍历序列分别为： DHEBFIGCA和DBEHAFCIG,则该二叉树对应的先序遍历序列为_和层次遍历序列为_。

根据中序遍历和后序遍历序列，可以得到该二叉树的结构如下：

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

其中，根据后序遍历序列，最后一个节点为根节点，即G；根据中序遍历序列，G的左边为其左子树的节点，右边为其右子树的节点，因此可以划分出左子树和右子树的中序遍历序列，分别为DBEHAFC和CIG。由于中序遍历中根节点在左子树和右子树的中序遍历序列中间，因此可以得到左右子树的后序遍历序列，分别为BEHDFA和IGHC。接下来可以分别对左右子树进行递归，重建整棵二叉树。

根据先序遍历的定义，先访问根节点，然后先序遍历左子树，最后先序遍历右子树。因此，该二叉树的先序遍历序列为CGDHEFABI，层次遍历序列为GCIDFBEAH。

相关问题

已知一棵二叉树的先序遍历和中序遍历的序列分别为：ABDEGCF和DBGEACF。 请画出此二叉树，并给出后序遍历序列。

二叉树的结构如下所示：

      A
    /   \
   B     C
  / \   / \
 D   E G   F

根据后序遍历的定义，我们可以得到后序遍历序列为：DGEBFCA。

具体解释：

对于当前给出的先序遍历序列 ABDEGCF，我们可以知道 A 是根节点，因此它在中序遍历序列中的位置为 D B G E A C F。

根据中序遍历序列，我们可以将二叉树分为两个子树，即左子树 DBGE 和右子树 ACF。

接下来，我们递归地对左子树和右子树进行相同的操作。

对于左子树，它的先序遍历序列为 BDEG，中序遍历序列为 DBGE。因此，B 是左子树的根节点，在它的左边是 D 和 E，在它的右边是 G。我们可以使用同样的方法构建左子树。

对于右子树，它的先序遍历序列为 CF，中序遍历序列为 ACF。因此，A 是右子树的根节点，在它的左边是 C，在它的右边是 F。我们可以使用同样的方法构建右子树。

最终，我们得到了如上所示的二叉树，并且它的后序遍历序列为 DGEBFCA。

设一棵二叉树的先序、中序遍历序列分别为： 先序：ABDFCEGH 中序：BFDAGEHC 则该二叉树的后序序列为：

根据先序遍历的性质，可以知道该二叉树的根节点是 A。然后根据中序遍历的性质，可以将其分为左子树和右子树：

左子树的中序遍历序列为 BFD，对应的先序遍历序列为 BDF。

右子树的中序遍历序列为 AGEHC，对应的先序遍历序列为 EGHAC。

然后对左右子树分别递归处理，得到左右子树的后序遍历序列，最后再加上根节点 A，即为整棵二叉树的后序遍历序列：

左子树的后序遍历序列为：DFB
右子树的后序遍历序列为：BGHECA
整棵二叉树的后序遍历序列为：DFBGHECA