原题

1020 Tree Traversals - PAT (Advanced Level) Practice

题目大意

输入n表示二叉树的元素数量，再分别输入该树的后序和中序遍历，输出该树的层序遍历。

解题思路

想了很久也没想出来怎么直接把后序中序转化为层序，大家如果有直接转化的方法欢迎讨论交流！

本题先将后序中序遍历转化为二叉树，再层序遍历二叉树。要构建给定后序和中序遍历的二叉树，可以按照以下步骤进行：

1. ​确定根节点：后序遍历的最后一个元素是当前子树的根节点。
2. ​分割中序数组：在中序遍历中找到根节点的位置，将数组分为左子树和右子树。
3. ​递归构建子树：根据中序分割的结果，确定左子树和右子树的大小，并在后序数组中划分对应的部分，递归构建左右子树。

代码(c++)

#include <bits/stdc++.h>
#include <vector>
#include <map>
#include <queue>using namespace std;typedef struct BiTNode {        // 定义二叉树int data;BiTNode *lchild, *rchild;
}BiTNode, *BiTree;BiTNode* buildTreeHelper(vector<int>& postorder, int postStart, int postEnd, int inStart, int inEnd, unordered_map<int, int>& inMap) {if (postStart > postEnd || inStart > inEnd) return nullptr;// 创建根节点BiTNode* root = new BiTNode();root->data = postorder[postEnd];int inRoot = inMap[root->data];int leftSubtreeSize = inRoot - inStart;// 递归构建左子树root->lchild = buildTreeHelper(postorder, postStart, postStart + leftSubtreeSize - 1, inStart, inRoot - 1, inMap);// 递归构建右子树root->rchild = buildTreeHelper(postorder, postStart + leftSubtreeSize, postEnd - 1, inRoot + 1, inEnd, inMap);return root;
}BiTree buildTree(vector<int>& postorder, vector<int>& inorder) {if (postorder.empty() || inorder.empty() || postorder.size() != inorder.size()) {return nullptr;}// 创建中序遍历的哈希映射，以便快速查找根节点位置。unordered_map<int, int> inMap;for (int i = 0; i < inorder.size(); ++i) inMap[inorder[i]] = i;return buildTreeHelper(postorder, 0, postorder.size() - 1, 0, inorder.size() - 1, inMap);
}void LevelOrderTraversal(BiTree root) {        // 层序遍历二叉树if (root == nullptr) return;queue<BiTNode*> q;q.push(root);cout << root->data;while (!q.empty()) {BiTNode* current = q.front();  q.pop();if (current != root) cout << " " << current->data;if (current->lchild != nullptr)q.push(current->lchild);if (current->rchild != nullptr)q.push(current->rchild);}
}int main() {int n;cin >> n;vector<int> postorder, inorder;for(int i = 0; i < n; i++) {int x;cin >> x;postorder.push_back(x);}for(int i = 0; i < n; i++) {int x;cin >> x;inorder.push_back(x);}BiTree root = buildTree(postorder, inorder);LevelOrderTraversal(root);
}