L2-006 树的遍历

---

问题描述

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

---

格式输入

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

---

格式输出

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

---

样例输入

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

---

样例输出

4 1 6 3 5 7 2

---

评测用例规模与约定

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

---

解析

方法思路
重建二叉树：后序遍历的最后一个元素是根节点，在中序遍历中找到这个根节点，根节点左边的部分是左子树的中序遍历，右边是右子树的中序遍历。根据左子树的节点数目，可以在后序遍历中分割出左子树和右子树的后序遍历。递归处理左右子树即可重建二叉树。

层序遍历：使用队列进行广度优先搜索（BFS），依次访问每一层的节点，并按顺序输出。

---

参考程序

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {if (inStart > inEnd || postStart > postEnd) return nullptr;int rootVal = postorder[postEnd];TreeNode* root = new TreeNode(rootVal);int inRoot = inMap[rootVal];int numsLeft = inRoot - inStart;root->left = buildTree(inorder, postorder, inStart, inRoot - 1, postStart, postStart + numsLeft - 1, inMap);root->right = buildTree(inorder, postorder, inRoot + 1, inEnd, postStart + numsLeft, postEnd - 1, inMap);return root;
}
vector<int> levelOrder(TreeNode* root) {vector<int> result;if (!root) return result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();result.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}   return result;
}
int main() {int N;cin >> N;vector<int> postorder(N);vector<int> inorder(N);for (int i = 0; i < N; ++i) {cin >> postorder[i];}for (int i = 0; i < N; ++i) {cin >> inorder[i];}unordered_map<int, int> inMap;for (int i = 0; i < N; ++i) {inMap[inorder[i]] = i;}TreeNode* root = buildTree(inorder, postorder, 0, N - 1, 0, N - 1, inMap);vector<int> level = levelOrder(root);for (int i = 0; i < level.size(); ++i) {if (i != 0) cout << " ";cout << level[i];}cout << endl;return 0;
}

难度等级

⭐️⭐️⭐️（1~10星）

以个人刷题整理为目的，如若侵权，请联系删除~