本关任务：实现 ConstructTree.cpp 里的TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)函数。 相关知识 给定一棵二叉树的前序遍历序列和中序遍历序列可以构造出这棵二叉树。例如前序序列是ABDECFG，中序序列是DBEAFCG，那么这颗二叉树的结构如图 1 所示。

根据前序遍历序列和中序遍历序列构造二叉树的具体实现如下：

TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2) {
    if(p1 > p2 || i1 > i2) return NULL; //边界条件，子树为空，返回 NULL
    TNode *root = new TNode; //申请根节点空间
    root->data = pa[p1]; //前序遍历序列的第一个元素为根节点
    int i = i1; //在中序遍历序列中查找根节点的位置
    while(ia[i] != pa[p1]) i++;
    root->left = InPreToTree(pa, ia, p1+1, p1+i-i1, i1, i-1); //构造左子树
    root->right = InPreToTree(pa, ia, p1+i-i1+1, p2, i+1, i2); //构造右子树
    return root;
}

首先判断边界条件，如果子树为空，返回 NULL。

然后申请根节点空间，将前序遍历序列的第一个元素作为根节点的值。

在中序遍历序列中查找根节点的位置，分别对左右子树递归调用 InPreToTree 函数构造子树，最终将左右子树连接到根节点上。

最后返回根节点指针。

注意：在 DeleteTree 函数中需要使用 delete 来删除节点，而不是 free。因为 TNode 是一个 C++ 结构体，使用 new 来申请空间，需要使用 delete 来释放空间。