利用c++设一棵二叉树以二叉链表表示， a) 实现递归方式由先序、中序序列构造二叉树的算法 b) 实现递归方式由后序、中序序列构造二叉树的算法

在C++中，我们可以利用二叉链表（也称为二叉树的顺序存储表示）来构建二叉树。下面分别给出利用先序、中序遍历序列以及后序、中序遍历序列递归地构造二叉树的算法。

**A) 先序遍历（根-左-右）+ 中序遍历构造二叉树**

**1. 递归算法**
- 先序遍历得到根节点
- 中序遍历找到根节点对应的分割点
- 递归构建左子树和右子树

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTreePreInorder(int* pre, int* inorder, int n) {
    if (pre[n - 1] == -1) { // 遍历结束标志
        return NULL;
    }
    TreeNode* root = new TreeNode(pre[0]);
    int inIndex = findInOrder(inorder, pre[0]); // 获取inorder中的位置
    root->left = buildTreePreInorder(pre + 1, inorder, inIndex); // 构建左子树
    root->right = buildTreePreInorder(pre + inIndex + 1, inorder, n); // 构建右子树
    return root;
}

// 辅助函数，在inorder数组中查找特定值的位置
int findInOrder(int* inorder, int target) {
    for (int i = 0; inorder[i] != -1; ++i) {
        if (inorder[i] == target) {
            return i;
        }
    }
    return -1;
}

**B) 后序遍历（左-右-根）+ 中序遍历构造二叉树**

**2. 递归算法**
- 后序遍历找到根节点（通过后序遍历可以确定左右子树已经构建）
- 使用中序遍历找到根节点的位置
- 递归构建左右子树

TreeNode* buildTreePostInorder(int* post, int* inorder, int n) {
    // 中序遍历的最后一个元素是根节点
    int rootVal = inorder[n - 1];
    int rootIndex = findInOrder(post, rootVal);

    TreeNode* root = new TreeNode(rootVal);
    root->left = buildTreePostInorder(post, inorder, rootIndex); // 左子树
    root->right = buildTreePostInorder(post + rootIndex + 1, inorder, n); // 右子树
    return root;
}

在这两个算法中，`pre[]`、`post[]`分别是先序和后序遍历的结果，`inorder[]`是中序遍历的结果，`n`代表数据的数量。注意，这些函数假设输入的数组中最后一位是-1，作为遍历结束的标志。