当前位置: 首页 > news >正文

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星)

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

http://www.xdnf.cn/news/9487.html

相关文章:

  • DHTMLX宣布推出支持 Redux、TypeScript 和 MUI 的 React Gantt甘特图控件
  • redis利用备忘录
  • Jsp技术入门指南【五】详细讲解jsp结构页面
  • 【含文档+PPT+源码】基于Python爬虫二手房价格预测与可视化系统的设计与实现
  • 论文阅读:2024 arxiv AI Safety in Generative AI Large Language Models: A Survey
  • 自然语言处理入门7——注意力机制
  • 数据结构——顺序表(C语言实现)
  • [250418] 智谱 AI 发布新一代模型,同时推出新域名 Z.ai
  • yocto编译使用共享缓存
  • IntelliSense 已完成初始化,但在尝试加载文档时出错
  • 前端单元测试实战:如何开始?
  • Vue2+Vue3 130~180集学习笔记
  • Google Colab测试部署Qwen大模型,实现PDF转MD场景OCR 识别(支持单机环境)
  • 迭代器模式:统一不同数据结构的遍历方式
  • ctf.show—Web(1-10)详细通关教程
  • 2025年行业AI Agent选型专业指南
  • RT-Thread RTThread studio 初使用
  • 零基础玩转AI数学建模:从理论到实战
  • LINUX学习——守护进程的含义及编程实现
  • Function Calling的机制 (含示例)
  • Sqlite3交叉编译全过程
  • 2025妈妈杯数学建模B题完整分析论文
  • 游戏引擎学习第233天
  • 【go】什么是Go语言中的GC,作用是什么?调优,sync.Pool优化,逃逸分析演示
  • 深度学习神经网络全连接笔记day1
  • 2025年03月中国电子学会青少年软件编程(Python)等级考试试卷(四级)真题
  • python flask 项目部署
  • 源码分析之Leaflet中Point
  • CSS 美化页面(五)
  • TikTok流量变现全攻略:免费与付费玩法解析