二叉树遍历：根据前序和中序遍历求后序遍历并画图

根据前序遍历和中序遍历求后序遍历并画图

题目：

已知一棵二叉树的前序遍历为'ABCDEFG'，中序遍历为'CBDAFGE'，求出后序遍历并画出图。

解题思路：

1. 后序遍历的定义： 后序遍历是指先遍历左子树，再遍历右子树，最后遍历根节点的顺序。
2. 利用前序和中序遍历确定根节点： 前序遍历的第一个节点是根节点，中序遍历中根节点位于左右子树之间。
3. 递归遍历左右子树： 根据根节点位置，将中序遍历划分为左右子树，并根据前序遍历确定左右子树的节点顺序，递归遍历左右子树。

解答：

后序遍历为：'CBDGEFBA'

树形图如下：

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

解释：

• 前序遍历'ABCDEFG'的第一个节点'A'为根节点。
• 中序遍历'CBDAFGE'中，根节点'A'位于'CBDA'和'FGE'之间，将中序遍历划分为左子树'CBDA'和右子树'FGE'。
• 前序遍历中，左子树节点为'BCDA'，右子树节点为'FGE'。
• 递归遍历左子树，得到左子树的后序遍历为'CBDA'。
• 递归遍历右子树，得到右子树的后序遍历为'FGE'。
• 根据后序遍历的定义，先遍历左子树'CBDA'，再遍历右子树'FGE'，最后遍历根节点'A'，最终得到后序遍历'CBDGEFBA'。