给定一棵满二叉树先序遍历的结果求该树中序遍历的输出结果编程实现

由于是满二叉树，可以通过递归的方式构造出中序遍历的结果。

具体地，假设当前树的先序遍历结果为 preorder，左子树的先序遍历结果为 left_preorder，右子树的先序遍历结果为 right_preorder，中序遍历结果为 inorder，根节点为 root。

则有以下递归关系：

1. 如果 preorder 为空，返回空列表。
2. 取出 preorder 的第一个元素作为根节点 root。
3. 找到 root 在 inorder 中的位置 index。
4. 构造左子树的先序遍历结果 left_preorder，从 preorder 的第二个元素开始，取 index 个元素。构造右子树的先序遍历结果 right_preorder，从 preorder 的第 index+1 个元素开始，取剩下的元素。
5. 递归调用函数，分别求出左子树的中序遍历结果 left_inorder 和右子树的中序遍历结果 right_inorder。
6. 将 left_inorder、root、right_inorder 拼接成 inorder，并返回。

具体实现如下：