用c++实现已知二叉树的先序遍历序列和中序遍历序列，求唯一的二叉树并输出后序遍历序列

要用C++实现已知二叉树的先序遍历序列和中序遍历序列，求唯一的二叉树并输出后序遍历序列，可以按照以下步骤进行： 1. 根据先序遍历序列和中序遍历序列构建二叉树。 2. 对构建好的二叉树进行后序遍历并输出结果。 以下是具体的实现代码： ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; // 定义二叉树节点结构 struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} }; // 根据先序遍历和中序遍历构建二叉树 TreeNode* buildTree(const vector<char>& preorder, const vector<char>& inorder, int preStart, int preEnd, int inStart, int inEnd, unordered_map<char, int>& inMap) { if (preStart > preEnd || inStart > inEnd) return nullptr; // 根节点是前序遍历的第一个节点 char rootVal = preorder[preStart]; TreeNode* root = new TreeNode(rootVal); // 在中序遍历中找到根节点的位置 int inRoot = inMap[rootVal]; int numsLeft = inRoot - inStart; // 递归构建左子树和右子树 root->left = buildTree(preorder, inorder, preStart + 1, preStart + numsLeft, inStart, inRoot - 1, inMap); root->right = buildTree(preorder, inorder, preStart + numsLeft + 1, preEnd, inRoot + 1, inEnd, inMap); return root; } // 后序遍历二叉树 void postorderTraversal(TreeNode* root, vector<char>& postorder) { if (root == nullptr) return; postorderTraversal(root->left, postorder); postorderTraversal(root->right, postorder); postorder.push_back(root->val); } int main() { // 示例输入 vector<char> preorder = {'A', 'B', 'D', 'E', 'C', 'F'}; vector<char> inorder = {'D', 'B', 'E', 'A', 'C', 'F'}; // 构建中序遍历的哈希映射 unordered_map<char, int> inMap; for (int i = 0; i < inorder.size(); ++i) { inMap[inorder[i]] = i; } // 构建二叉树 TreeNode* root = buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1, inMap); // 后序遍历并输出结果 vector<char> postorder; postorderTraversal(root, postorder); for (char c : postorder) { cout << c << " "; } cout << endl; return 0; } ``` 这段代码首先根据先序遍历序列和中序遍历序列构建二叉树，然后对构建好的二叉树进行后序遍历并输出结果。