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

江干区住房和城市建设局网站北京网页设计有限公司

江干区住房和城市建设局网站,北京网页设计有限公司,wordpress微信qq登录,免费动画模板素材网站树的遍历 给定一棵二叉树的后序遍历和中序遍历#xff0c;请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式#xff1a; 输入第一行给出一个正整数 N ( ≤ 30 ) N(≤30) N(≤30)#xff0c;是二叉树中结点的个数。第二行给出其后序遍历序列。第三…树的遍历 给定一棵二叉树的后序遍历和中序遍历请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式 输入第一行给出一个正整数 N ( ≤ 30 ) N(≤30) 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解题 在后序遍历序列中根节点总是在最后一个位置而在中序遍历序列中根节点将序列分为左右两部分分别对应左子树和右子树。 因此我们可以利用两个数组的信息递归构建二叉树然后再进行层序遍历。 Java import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner;// 结点类 class TreeNode {int val; // 值TreeNode left; // 左孩子TreeNode right; // 右孩子TreeNode(int x) {val x;} }public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt();int[] postOrder new int[N];int[] inOrder new int[N];for (int i 0; i N; i) {postOrder[i] scanner.nextInt();}for (int i 0; i N; i) {inOrder[i] scanner.nextInt();}// 根据后序遍历结果和前序遍历结果构建二叉树TreeNode root helper(postOrder, inOrder);// 层序遍历ListInteger ans levelOrderTraversal(root);// 输出结果for (int i 0; i ans.size(); i) {System.out.print(ans.get(i));if (i ans.size() - 1) {System.out.print( );}}scanner.close();}// 检查是否有某个序列为空private static TreeNode helper(int[] postOrder, int[] inOrder) {if (postOrder null || inOrder null || postOrder.length 0 || inOrder.length 0) {return null;}return buildTree(postOrder, 0, postOrder.length - 1, inOrder, 0, inOrder.length - 1);}/*** 构建二叉树* param postOrder 后序遍历结果* param postStart 后序遍历序列的起始位置* param postEnd 后序遍历序列的结束位置* param inOrder 中序遍历结果* param inStart 中序遍历序列的起始位置* param inEnd 中序遍历序列的结束位置* return 构建的二叉树的根节点*/private static TreeNode buildTree(int[] postOrder, int postStart, int postEnd, int[] inOrder, int inStart, int inEnd) {// (0) 终止条件此时没有结点了返回空树if (postStart postEnd || inStart inEnd) {return null;}// (1) 先找到根结点后序遍历的最后一个结点int rootVal postOrder[postEnd];TreeNode root new TreeNode(rootVal);// (2) 在中序遍历序列中找到根结点的位置int rootIndexInInOrder 0;for (int i inStart; i inEnd; i) {if (inOrder[i] rootVal) {rootIndexInInOrder i;break;}}// (3) 计算左子树的结点个数int leftTreeSize rootIndexInInOrder - inStart;// (4) 递归构建左子树和右子树root.left buildTree(postOrder, postStart, postStart leftTreeSize - 1, inOrder, inStart, rootIndexInInOrder - 1);root.right buildTree(postOrder, postStart leftTreeSize, postEnd - 1, inOrder, rootIndexInInOrder 1, inEnd);// (5) 返回根结点return root;}// 层序遍历二叉树private static ListInteger levelOrderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null) {return result;}// 创建队列用于层序遍历QueueTreeNode queue new LinkedList();queue.offer(root);// 循环遍历队列中的结点while (!queue.isEmpty()) {TreeNode node queue.poll();// 将当前结点的值加入结果列表result.add(node.val);if (node.left ! null) {queue.offer(node.left); // 将左子结点加入队列}if (node.right ! null) {queue.offer(node.right); // 将右子结点加入队列}}return result;} }C #include iostream #include vector #include queue using namespace std;// 结点类 class TreeNode { public:int val; // 值TreeNode *left; // 左孩子TreeNode *right; // 右孩子TreeNode(int x) {val x;left nullptr;right nullptr;} };// 构建二叉树 TreeNode* buildTree(vectorint postOrder, int postStart, int postEnd, vectorint inOrder, int inStart, int inEnd) {// 终止条件此时没有结点了返回空树if (postStart postEnd || inStart inEnd) {return nullptr;}// 先找到根结点后序遍历的最后一个结点int rootVal postOrder[postEnd];TreeNode* root new TreeNode(rootVal);// 在中序遍历序列中找到根结点的位置int rootIndexInInOrder 0;for (int i inStart; i inEnd; i) {if (inOrder[i] rootVal) {rootIndexInInOrder i;break;}}// 计算左子树的结点个数int leftTreeSize rootIndexInInOrder - inStart;// 递归构建左子树和右子树root-left buildTree(postOrder, postStart, postStart leftTreeSize - 1, inOrder, inStart, rootIndexInInOrder - 1);root-right buildTree(postOrder, postStart leftTreeSize, postEnd - 1, inOrder, rootIndexInInOrder 1, inEnd);// 返回根结点return root; }// 层序遍历二叉树 vectorint levelOrderTraversal(TreeNode* root) {vectorint result;if (root nullptr) {return result;}// 创建队列用于层序遍历queueTreeNode* q;q.push(root);// 循环遍历队列中的结点while (!q.empty()) {TreeNode* node q.front();q.pop();// 将当前结点的值加入结果列表result.push_back(node-val);if (node-left ! nullptr) {q.push(node-left); // 将左子结点加入队列}if (node-right ! nullptr) {q.push(node-right); // 将右子结点加入队列}}return result; }int main() {int N;cin N;vectorint postOrder(N);vectorint inOrder(N);for (int i 0; i N; i) {cin postOrder[i];}for (int i 0; i N; i) {cin inOrder[i];}// 根据后序遍历结果和中序遍历结果构建二叉树TreeNode* root buildTree(postOrder, 0, N - 1, inOrder, 0, N - 1);// 层序遍历vectorint ans levelOrderTraversal(root);// 输出结果for (int i 0; i ans.size(); i) {cout ans[i];if (i ans.size() - 1) {cout ;}}return 0; }测试链接L2-006 树的遍历
http://www.pierceye.com/news/754049/

相关文章:

  • 网站建设贰金手指科捷6构建一个网站需要什么
  • wordpress 插件下载站seo网站布局
  • 公司网站建设费用会计入账招代理的网站建设公司
  • 查询网站入口中廉建设网站
  • 在市场部做网站多少工资微网站需要域名吗
  • 做网站有没有前景WordPress 长文 阅读
  • 按揭车在哪个网站可以做贷款网页素材制作
  • 做网站公司怎样wordpress 速度优化
  • 网站建设必须要主机吗程序员外包公司是什么意思
  • 百度入口的链接seo赚钱培训
  • 利川网站建设wordpress 文章音频
  • 对电子商务网站建设与管理的理解福州市建设工程造价管理网站
  • 网站登录系统内部错误建设机械网站案例分析
  • 网络营销网站建设培训乔拓云的品牌推广方案
  • 狼雨seo网站河北省建设集团有限公司网站首页
  • 如何建双注册网站一嗨租车网站建设的功能特色
  • 陕西正天建设有限公司网站wordpress 筛选
  • 产品展示网站方案2022年国内重大新闻
  • 网站的支付接口对接怎么做深圳品牌网站建设服务
  • 哈尔滨网站快速排名网站采集被降权
  • 做网站要钱吗学校网站建设调查问卷
  • 重庆网站建设招标网站建设网站建设教程
  • 权威的广州h5网站seo网站分析工具
  • 美食网站要怎么做游戏优化大师下载安装
  • vip解析网站怎么做的做网站需要注册商标多少类
  • 一般做网站宽高多少网页调用 wordpress 图片编辑器
  • 简述网站建设的基本过程word模板免费下载网站
  • 页面好看的蛋糕网站wordpress路由插件
  • 网站建站四种方案深圳网站建设维护
  • 企业网站优化的方案游戏网页设计图片