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

企业信用信息查询系统入口seo优化公司哪家好

企业信用信息查询系统入口,seo优化公司哪家好,ck播放器整合WordPress,wordpress 360字体给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 题目中是给定两个数组,一个是存放这颗树的前序遍历的数组,一个是存放这棵树的…

       给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

       题目中是给定两个数组,一个是存放这颗树的前序遍历的数组,一个是存放这棵树的中序遍历的数组,解这道题的关键我们首先要知道树的前中序遍历分别指的是什么?它们两者之间到底存在着什么关系?解下来让我们一探究竟

前序遍历

       前序遍历的遍历顺序是中左右,先遍历自己,后遍历自己的左子树,最后再遍历自己的右子树,由上图已知该树的前序遍历为[3,9,20,15,7]

中序遍历

       中序遍历的遍历顺序是左中右,先遍历左子树,后遍历自己,最后再遍历自己的右子树,由上图已知该树的中序遍历为[9,3,15,20,7]

 观看这两个数组,有没有发现什么特别的地方?

       树是一种天然的递归结构,每棵子树也可以称为一棵独立的树,根据上图我们不难发现,数组中的元素是严格按照中左右的顺序填充的

 

 根据上图我们不难发现,数组中的元素是严格按照中左右的顺序填充的

所以我们再来看这两个数组的特点:

 我们已经得知了这两个数组中的相存的特点,接下来就可以撸代码了

  • 我们要通过数组中的元素值得到该元素在数组中的索引为位置,所们先要使用Map结构的数据结构去对我们的中序遍历时的数据进行预处理
 Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}
  • 然后开始我们的构建函数dfs(前序数组,前序开始的位置,前序结束的位置,中序数组,中序开始的位置,中序结束的位置)
 return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
  • 递归时如果出先了开始位置比结束位置还要大的时候,这种情况肯定是不满足我们的条件的,所以直接抛出null就可以了
if(pStart>pEnd||iStart>iEnd){return null;}
  • 通过前序遍历数组拿到我们相对根节点,然后通过map去查询我们中序数组中我们的相对根节点的索引index,因为我们的中序遍历是左中右,所以中序遍历中的index-iStart的长度就是我们相对子树的节点的个数
 int val=preorder[pStart];TreeNode root=new TreeNode(val);int size=map.get(val);int length=size-iStart;
  • 最后开始dfs,构造左右子树,这道题就完成了
    //     不包括当前的根结点   前序取不到起点(左开右闭)   中序取不到终点(左闭右开)root.left=dfs(preorder,pStart+1,pStart+length,inorder,iStart,size-1);//                  左子树下一次递归的起点 root.right=dfs(preorder,pStart+length+1,pEnd,inorder,size+1,iEnd);//                  右子树下一次递归的起点

接下来上源码供大家参考:

  Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder==null||inorder==null){return null;}for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode dfs(int[] preorder,int pStart,int pEnd,int[]inorder,int iStart,int iEnd){if(pStart>pEnd||iStart>iEnd){return null;}int val=preorder[pStart];TreeNode root=new TreeNode(val);int size=map.get(val);int length=size-iStart;root.left=dfs(preorder,pStart+1,pStart+length,inorder,iStart,size-1);root.right=dfs(preorder,pStart+length+1,pEnd,inorder,size+1,iEnd);return root;}

http://www.15wanjia.com/news/18523.html

相关文章:

  • 网站怎样做支付接口市场调研报告1000字
  • 老鹰画室网站哪家做的百度搜索推广方法
  • 渝中集团网站建设福州网seo
  • 近期的新闻热点网站推广优化怎么做最好
  • 做经营行网站需要什么手续绍兴seo排名收费
  • 平台网站做数据维护需要多久网络营销典型案例
  • 用做网站使用的图片百度霸屏推广一般多少钱
  • wordpress可视化编辑失效江西seo
  • 东莞信息网宁波seo网站排名
  • 网站建设与制作外包服务友情链接对网站的作用
  • 上海网站优化哪家好关键词优化推广
  • 天津 交友 网站建设网站seo运营培训机构
  • 刷数据网站怎么推广seo关键词怎么选
  • 珠宝设计制作培训seo值是什么意思
  • wordpress网站如何找相似图片 识别
  • wordpress 显示子分类百度seo排名优化是什么
  • 大学生网站规划建设搭建网站的五大步骤
  • wordpress debug模式小小课堂seo自学网
  • 做网站能挣钱成都网站推广哪家专业
  • 网站手机站怎么做的湘潭网站seo磐石网络
  • 京东企业的电子网站建设株洲seo排名
  • 滁州网站开发czesou湘潭网络推广
  • wordpress本地浏览慢郑州百度网站快速优化
  • 做房地产网站建设百度教育网站
  • 谁做网站如何自己建个网站
  • 本机部署wordpress超慢湖南企业竞价优化服务
  • 简单的网页设计网站广州疫情最新情况
  • 免费手机个人网站潍坊自动seo
  • 上海抖音推广seo智能优化
  • 网站留言表格怎么做百度词条优化