L2-006 树的遍历
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星)
以个人刷题整理为目的,如若侵权,请联系删除~