C++ 二叉树层序遍历：给定后序遍历和中序遍历

思路：\n1. 根据后序遍历和中序遍历构建二叉树；\n2. 层序遍历二叉树。\n\n具体实现：\n1. 定义二叉树的节点结构体Node，包含键值和左右子节点指针；\n2. 根据后序遍历和中序遍历构建二叉树的函数buildTree，递归实现；\n - 后序遍历的最后一个节点是根节点，在中序遍历中找到根节点的位置；\n - 根据根节点的位置，将中序遍历分成左右两部分，分别对应左子树和右子树；\n - 根据左右子树的节点个数，在后序遍历中确定左右子树的范围；\n - 递归构建左右子树；\n3. 层序遍历二叉树的函数levelOrder，使用队列实现；\n - 将根节点入队；\n - 循环直到队列为空，每次出队一个节点，将其值输出，并将其左右子节点入队；\n4. 主函数中读取输入，调用buildTree构建二叉树，再调用levelOrder输出层序遍历的序列。\n\n代码实现如下：\n\nc++\n#include <iostream>\n#include <queue>\nusing namespace std;\n\nstruct Node {\n int val;\n Node* left;\n Node* right;\n Node(int x) : val(x), left(NULL), right(NULL) {}\n};\n\nNode* buildTree(vector<int>& postorder, vector<int>& inorder, int postStart, int postEnd, int inStart, int inEnd) {\n if (postStart > postEnd || inStart > inEnd) {\n return NULL;\n }\n int rootVal = postorder[postEnd];\n Node* root = new Node(rootVal);\n int rootIndex;\n for (int i = inStart; i <= inEnd; i++) {\n if (inorder[i] == rootVal) {\n rootIndex = i;\n break;\n }\n }\n int leftNum = rootIndex - inStart;\n root->left = buildTree(postorder, inorder, postStart, postStart + leftNum - 1, inStart, rootIndex - 1);\n root->right = buildTree(postorder, inorder, postStart + leftNum, postEnd - 1, rootIndex + 1, inEnd);\n return root;\n}\n\nvoid levelOrder(Node* root) {\n if (root == NULL) {\n return;\n }\n queue<Node*> q;\n q.push(root);\n while (!q.empty()) {\n Node* node = q.front();\n q.pop();\n cout << node->val << " ";\n if (node->left) {\n q.push(node->left);\n }\n if (node->right) {\n q.push(node->right);\n }\n }\n}\n\nint main() {\n int N;\n cin >> N;\n vector<int> postorder(N), inorder(N);\n for (int i = 0; i < N; i++) {\n cin >> postorder[i];\n }\n for (int i = 0; i < N; i++) {\n cin >> inorder[i];\n }\n Node* root = buildTree(postorder, inorder, 0, N - 1, 0, N - 1);\n levelOrder(root);\n return 0;\n}\n