利用二叉树的前序和中序遍历，给出二叉树的后序遍历

题目描述
利用二叉树的前序和中序遍历，给出二叉树的后序遍历
输入
第一行树的个数; 前序和中序遍历各占一行，元素为整数，使用空格分隔
输出
后序遍历。占一行，每个元素之后输出一个空格
样例输入 Copy
1
2 1 3
1 2 3
样例输出 Copy
1 3 2

理解先序遍历中序遍历思想，先序遍历访问顺序：根节点左孩子右有孩子，中序遍历：左根右，后序：左右根，去推吧

• 以下回答由chatgpt基于相关博客总结生成:

  我可以回答这个问题。具体来说，利用二叉树的前序和中序遍历来得到二叉树的后序遍历的步骤如下：

  1. 接收输入。输入应为二叉树的前序遍历和中序遍历，可以用数组或字符串来表示。

  2. 根据前序遍历（父节点-左节点-右节点）确定二叉树的根节点，并在中序遍历中找到该根节点的位置，把中序遍历分为左子树和右子树两部分。

  3. 对左子树进行递归操作，重复步骤1，直到左子树只有一个节点为止。

  4. 对右子树进行递归操作，重复步骤1，直到右子树只有一个节点为止。

  5. 将左子树的后序遍历和右子树的后序遍历合并，即可得到整个树的后序遍历。

  下面是一个样例输入和相应的输出，假设输入的前序遍历为[1,2,4,5,3,6,7]，中序遍历为[4,2,5,1,6,3,7]：

  • 确定根节点为1。
  • 将中序遍历分为左子树[4,2,5]和右子树[6,3,7]。
  • 对左子树进行递归操作，确定该子树的根节点为2，将中序遍历分为左子树[4]和右子树[5]，递归结束。
  • 对右子树进行递归操作，确定该子树的根节点为3，将中序遍历分为左子树[6]和右子树[7]，递归结束。
  • 合并左子树和右子树的后序遍历，得到[4,5,2,6,7,3,1]，即整个树的后序遍历。

  最后，需要注意的是，在实现过程中需要处理好数组或字符串的下标问题。代码实现可以用递归或栈来实现。