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

宁德网站开发环球军事网最新消息

宁德网站开发,环球军事网最新消息,竭诚网络网站建设公司,深圳高端企业官方网站建设👑专栏内容:力扣刷题⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、题目描述1、题目2、示例 二、题目分析1、递归2、栈 一、题目描述 1、题目 剑指offer:重建二叉树 给定节…

在这里插入图片描述

  • 👑专栏内容:力扣刷题
  • ⛪个人主页:子夜的星的主页
  • 💕座右铭:前路未远,步履不停

目录

  • 一、题目描述
    • 1、题目
    • 2、示例
  • 二、题目分析
    • 1、递归
    • 2、栈


一、题目描述

1、题目

剑指offer:重建二叉树

给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。
在这里插入图片描述

提示:
1.vin.length == pre.length
2.previn 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点,系统会自动输出整颗树做答案对比
数据范围: n < = 2000 n<=2000 n<=2000,节点的值 − 1000 < = v a l < = 1000 -1000<=val<=1000 1000<=val<=1000
要求:时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)

2、示例

示例1

输入:[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值:{1,2,3,4,#,5,6,#,7,#,#,8}
说明:返回根节点,系统会输出整颗二叉树对比结果,重建结果如题面图示    

示例2

输入:[1],[1]
返回值:{1}

示例3

输入:[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值:{1,2,5,3,4,6,7}

二、题目分析

1、递归

public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {int n = pre.length;int m = vin.length;if(n == 0 || m == 0) return null;//构建根节点TreeNode root = new TreeNode(pre[0]);for(int i = 0; i < vin.length; i++){//找到中序遍历中的前序第一个元素if(pre[0] == vin[i]){ //构建左子树root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); //构建右子树root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));break;}}return root;}
}

2、栈

请添加图片描述

public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {int n = pre.length;int m = vin.length;//每个遍历都不能为0if(n == 0 || m == 0) return null;Stack<TreeNode> s = new Stack<TreeNode>();//首先建立前序第一个即根节点TreeNode root = new TreeNode(pre[0]); TreeNode cur = root;for(int i = 1, j = 0; i < n; i++){//要么旁边这个是它的左节点if(cur.val != vin[j]){ cur.left = new TreeNode(pre[i]);s.push(cur);//要么旁边这个是它的右节点,或者祖先的右节点cur = cur.left; }else{j++;//弹出到符合的祖先while(!s.isEmpty() && s.peek().val == vin[j]){cur = s.pop();j++;}//添加右节点cur.right = new TreeNode(pre[i]); cur = cur.right;}}return root;}
}
http://www.shuangfujiaoyu.com/news/20084.html

相关文章:

  • 网站上的定位功能如何实现的网站运维
  • h5网站的优势百度营销客户端
  • 邮箱163注册青岛快速排名优化
  • 哪里有专业做网站河南网站seo靠谱
  • 网站设计服务表app平台搭建需要多少钱
  • 如何建一个视频网站微信广点通广告平台
  • 广州建设工程交易中心改版西安seo按天收费
  • 16岁学生免费开网店seo推广软件排行榜
  • 网站右击无效是怎么做的网站流量排行
  • 怎么运用区块链做网站seo的优化原理
  • 惠东网络建站公司宁波关键词优化平台
  • 嘉兴做网站哪家好市场推广工作内容
  • 南海佛山网站建设一份完整的活动策划方案
  • 网络营销导向企业网站建设的原则郑州seo线下培训
  • 用一个口罩做一把枪宁波seo服务推广
  • 知名网站建设平台如何在网上推广自己的产品
  • 网站欢迎页面 特效app接入广告变现
  • wordpress网站刷新广告信息发布平台
  • 山东大汉建设机械有限公司网站关于友谊的连接
  • 网站支持asp深圳最好的外贸seo培训
  • 哈尔滨网站公司网站seo排名
  • 衡水市网站建设app优化建议
  • wordpress 动态网站模板下载地址无货源电商怎么做
  • 老外做中文网站域名检测
  • 新网站如何做免费推广怎么做盲盒
  • 济南网站建设大标网络济南优化网站关键词
  • 义乌seo新网站seo外包
  • 网站优化费用怎么做会计分录公司员工培训方案
  • 网站设计制造全面的seo网站优化排名
  • 上海工商管理局官网百度seo和sem