C++根据二叉树的先序遍历序列和中序遍历序列，求其后序遍历序列

我们可以利用递归的思想来解决这个问题。一个二叉树的先序遍历序列的第一个元素一定是根节点，而在中序遍历序列中，根节点的左侧都是左子树的节点，右侧都是右子树的节点。因此，我们可以根据这个性质来构建二叉树，并且递归地处理左右子树。

具体的实现步骤如下：

1. 根据先序遍历序列的第一个元素创建根节点。
2. 在中序遍历序列中找到根节点的位置，将序列分成左右两部分。
3. 递归地处理左子树，将左子树的先序遍历序列和中序遍历序列作为参数传入。
4. 递归地处理右子树，将右子树的先序遍历序列和中序遍历序列作为参数传入。
5. 将根节点的值加入到后序遍历序列中。
6. 返回后序遍历序列。

下面是 C++ 的代码实现：

#include <vector>
#include <unordered_map>

using namespace std;

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

class Solution {
public:
    vector<int> buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 将中序遍历序列的每个元素及其下标存储到哈希表中
        for (int i = 0; i < inorder.size(); i++) {
            index[inorder[i]] = i;
        }
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

private:
    unordered_map<int, int> index;

    // 根据先序遍历序列和中序遍历序列构建二叉树，并返回后序遍历序列
    vector<int> buildTree(vector<int>& preorder, int preStart, int preEnd,
                          vector<int>& inorder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return {};
        }
        // 先序遍历序列的第一个元素是根节点
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        // 在中序遍历序列中找到根节点的位置
        int rootIndex = index[rootVal];
        // 计算左子树的长度
        int leftSize = rootIndex - inStart;
        // 递归处理左子树
        vector<int> left = buildTree(preorder, preStart + 1, preStart + leftSize,
                                     inorder, inStart, rootIndex - 1);
        // 递归处理右子树
        vector<int> right = buildTree(preorder, preStart + leftSize + 1, preEnd,
                                      inorder, rootIndex + 1, inEnd);
        // 将根节点的值加入到后序遍历序列中
        vector<int> res = left;
        res.insert(res.end(), right.begin(), right.end());
        res.push_back(rootVal);
        return res;
    }
};

时间复杂度为 O(n)，其中 n 是二叉树中的节点个数。这是因为我们需要遍历每个节点恰好一次。空间复杂度为 O(n)，其中 n 是二叉树中的节点个数。除了存储答案所需的空间，我们还需要 O(n) 的空间存储哈希表。