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

在C++中，我们可以使用结构体定义二叉树节点，并通过链表的方式存储左右子节点。以下是两种常见情况下的二叉树构造算法：

**a) 由先序遍历和中序遍历构造二叉树**

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

TreeNode* buildTreeFromPreInOrder(vector<int>& preorder, vector<int>& inorder, int start, int end) {
    if (start > end) return nullptr;
    
    // 先序遍历的第一个元素作为根节点
    TreeNode* root = new TreeNode(preorder[start]);
    
    // 找到该根节点在中序遍历中的索引
    int index = searchInOrder(inorder, start, root->val);

    // 分别在左子树和右子树中递归构造
    root->left = buildTreeFromPreInOrder(preorder, inorder, start + 1, index - 1);
    root->right = buildTreeFromPreInOrder(preorder, inorder, index + 1, end);

    return root;
}

int searchInOrder(vector<int>& arr, int start, int target) {
    for (int i = start; i < arr.size(); ++i) {
        if (arr[i] == target) return i;
    }
    return -1;
}

**b) 由后序遍历和中序遍历构造二叉树**

后序遍历先访问左子树，再访问右子树，最后访问根节点，所以我们需要先找到根节点的位置，然后用剩余的后序遍历来确定左子树和右子树。

TreeNode* buildTreeFromPostInOrder(vector<int>& postorder, vector<int>& inorder, int start, int end) {
    if (start > end) return nullptr;
    
    // 后序遍历最后一个元素为根节点，查找它的位置
    int index = findLastNodeIndex(postorder, inorder, start, end);
    TreeNode* root = new TreeNode(postorder[index]);

    // 在中序遍历中找到这个元素的位置
    index = searchInOrder(inorder, start, root->val);

    // 左右子树分别在前半部分和后半部分构建
    root->left = buildTreeFromPostInOrder(postorder, inorder, start, index - 1);
    root->right = buildTreeFromPostInOrder(postorder, inorder, index + 1, end);

    return root;
}

int findLastNodeIndex(vector<int>& arr, vector<int>& inorder, int start, int end) {
    // 在中序遍历中找到后序遍历的最后一个元素
    for (int i = start; i <= end; ++i) {
        if (findLastNodeIndexHelper(arr, inorder, start, i - 1, &index)) break;
    }
    return index;
}
bool findLastNodeIndexHelper(vector<int>& arr, vector<int>& inorder, int from, int to, int* index) {
    if (from > to) return false;
    for (int i = from; i <= to; ++i) {
        if (arr[*index] == inorder[i]) {
            *index += 1;
            if (!findLastNodeIndexHelper(arr, inorder, i + 1, to, index)) return false;
            break;
        }
    }
    return true;
}