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

LeetCode105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

文章目录

      • [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
        • 一、题目
        • 二、题解


一、题目

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

示例 1:
在这里插入图片描述

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorderinorder无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

二、题解

算法思路

我们要根据给定的前序遍历和中序遍历序列构建出一棵二叉树。前序遍历序列告诉我们根节点的值以及左子树和右子树的分割点,中序遍历序列告诉我们左子树和右子树的节点排列顺序。我们可以通过递归的方法来实现构建二叉树的过程。

具体步骤如下:

  1. 从前序遍历序列中取出第一个元素,它是当前子树的根节点的值。
  2. 在中序遍历序列中找到该根节点的值,根据这个值,将中序序列划分为左子树部分和右子树部分。
  3. 根据左子树和右子树的节点数量,在前序遍历序列中划分出左子树的前序序列和右子树的前序序列。
  4. 递归地构建左子树和右子树。

具体实现

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// 基准情况:如果前序遍历序列为空,返回空指针表示空树if (preorder.size() == 0) {return nullptr;}// 创建当前子树的根节点TreeNode *root = new TreeNode();root->val = preorder[0];// 在中序遍历序列中找到根节点的位置int index = 0;for (index = 0; index < inorder.size(); index++) {if (inorder[index] == preorder[0]) {break;}}// 划分左子树和右子树的序列vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + index + 1);vector<int> leftInorder(inorder.begin(), inorder.begin() + index);vector<int> rightPreorder(preorder.begin() + index + 1, preorder.end());vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());// 递归构建左子树和右子树root->left = buildTree(leftPreorder, leftInorder);root->right = buildTree(rightPreorder, rightInorder);return root;}
};

算法分析

  • 时间复杂度:在每次递归中,我们都需要遍历中序遍历序列来找到根节点的位置,这需要 O(n) 的时间,其中 n 是节点数量。递归的总时间复杂度取决于递归的层数以及每层的操作,因此总体时间复杂度为 O(n)。

  • 空间复杂度:每次递归都会创建新的前序和中序序列,空间复杂度主要取决于递归的深度,最坏情况下递归深度为 n,所以空间复杂度为 O(n)。此外,还需要存储二叉树节点的空间,所以总体空间复杂度也为 O(n)。

相关文章:

LeetCode105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树 文章目录 [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)一、题目二、题解 一、题目 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preo…...

编码技巧——Sentinel的blockHandler与fallback

本文介绍Sentinel的blockHandler与fallback的区别&#xff0c;背景是&#xff1a;发生限流时&#xff0c;配置的sentinel的blockhandler没有生效而fallback生效了&#xff1b;排查原因&#xff0c;从而给出Sentinel配置异常降级和限流降级的代码写法&#xff1b; 在查看源码前…...

最新成果展示:GaN基Micro-LED热学模型数据库的开发及应用

由于GaN基Micro-LED表面积-体积比增加&#xff0c;其在热学方面的性质有别于大尺寸的LED&#xff0c;如缺陷复合导致的热效应将在发光区域中产生诸多“热”点&#xff0c;导致发光波长不均匀&#xff0c;这将影响后期显示系统的成像稳定性。针对上述问题&#xff0c;天津赛米卡…...

【Vue3】动态组件

动态组件的基本使用 动态组件&#xff08;Dynamic Components&#xff09;是一种在 Vue 中根据条件或用户输入来动态渲染不同组件的技术。 在 Vue 中使用动态组件&#xff0c;可以使用 元素&#xff0c;并通过 is 特性绑定一个组件的名称或组件对象。通过在父组件中改变 is 特…...

Java超级玛丽小游戏制作过程讲解 第五天 创建并完成常量类04

//加载障碍物 try {obstacle.add(ImageIO.read(new File(path"brick.png")));obstacle.add(ImageIO.read(new File(path"soil_up.png")));obstacle.add(ImageIO.read(new File(path"soil_base.png"))); } catch (IOException e) {e.printStackTr…...

设置浏览器兼容

浏览器兼容 css兼容 cursor定义手型  Firefox不支持hand&#xff0c;IE支持pointer  解决方法&#xff1a;统一使用pointercss透明  IE&#xff1a;filter:progid:DXImageTransform.Microsoft.Alpha(style0,opacity60)  Firefox&#xff1a;opacity&#xff1a;0.6  解决…...

Java # List

ArrayList<>() import java.util.ArrayList; // 引入 ArrayList 类ArrayList<E> objectName new ArrayList<>();  // 初始化 常用方法 方法描述add()将元素插入到指定位置的 arraylist 中addAll()添加集合中的所有元素到 arraylist 中clear()删除 arrayl…...

git原理与使用

目录 引入基本操作分支管理远程操作标签管理 引入 假设你的老板要你设计一个文档&#xff0c;当你设计好了&#xff0c;拿给他看时&#xff0c;他并不是很满意&#xff0c;就要你拿回去修改&#xff0c;你修改完后&#xff0c;再给他看时&#xff0c;他还是不满意&#xff0c;…...

【C语言题解】将一句话的单词进行倒置,标点不倒置。

题目描述&#xff1a;将一句话的单词进行倒置&#xff0c;标点不倒置。比如 “I like beijing.”&#xff0c;经过处理后变为&#xff1a;“beijing. like I”。 文章目录 原题目题目描述&#xff1a;输入描述&#xff1a;输出描述&#xff1a;题目链接&#xff1a; 整体思路分…...

Postman 的简单使用

什么是Postman 在程序开发中用于调试网络程序或者跟踪网页请求。可以对网页进行简单的基本信息调试。Postman最早是作用chrome浏览器插件存在的&#xff0c;但是2018年初Chrome停止对Chrome应用程序的支持。所以现在Postman提供了独立的安装包&#xff0c;不再依赖于Chrome浏览…...

在CentOS7安装部署GitLab服务

CentOS 7 安装 Gitlab 官方安装教程&#xff1a;https://about.gitlab.com/install/ 参考安装教程&#xff1a;https://developer.aliyun.com/article/74395 安装配置 Step1&#xff1a;配置yum源 vim /etc/yum.repos.d/gitlab-ce.repo存入以下内容&#xff1a; [gitlab-c…...

订单系统就该这么设计,稳的一批~

订单功能作为电商系统的核心功能&#xff0c;由于它同时涉及到前台商城和后台管理系统&#xff0c;它的设计可谓是非常重要的。就算不是电商系统中&#xff0c;只要是涉及到需要交易的项目&#xff0c;订单功能都具有很好的参考价值&#xff0c;说它是通用业务功能也不为过。今…...

Agents改变游戏规则,亚马逊云科技生成式AI让基础模型加速工作流

最近&#xff0c;Stability AI正式发布了下一代文生图模型——Stable Diffusion XL 1.0这次的1.0版本是Stability AI的旗舰版生图模型&#xff0c;也是最先进的开源生图模型。 在目前的开放式图像模型中&#xff0c;SDXL 1.0是参数数量最多的。官方表示&#xff0c;这次采用的…...

详细教程:如何搭建废品回收小程序

废品回收是一项环保举措&#xff0c;通过回收和再利用废弃物品&#xff0c;可以减少资源浪费和环境污染。近年来&#xff0c;随着智能手机的普及&#xff0c;小程序成为了推广和运营的重要工具。本文将详细介绍如何搭建一个废品回收小程序。 1. 进入乔拓云网后台 首先&#xf…...

什么是双亲委派机制?

什么是双亲委派机制&#xff1f; Parent Delegation Model &#xff0c;直译过来可能叫做父级委托模型更容易理解 类的加载过程 Java 编译器将 Java源文件编译成.class 文件再由 JVM 加载 .class 文件到内存中JVM 装载完成后得到一个 Class 字节码对象拿到字节码对象之后 &a…...

Mageia 9 RC1 正式发布,Mandriva Linux 发行版的社区分支

导读Mageia 9 首个 RC 已发布。公告写道&#xff0c;自 2023 年 5 月发布 beta 2 以来&#xff0c;Mageia 团队一直致力于解决许多顽固问题并提供安全修复和新特性。 新版本的控制中心添加了用于删除旧内核的新功能&#xff0c;该功能在 Mageia 9 中默认自动启用&#xff0c;用…...

ChatGPT: 人机交互的未来

ChatGPT: 人机交互的未来 ChatGPT背景ChatGPT的特点ChatGPT的应用场景结论 ChatGPT ChatGPT是一种基于大数据和机器学习的人工智能聊天机器人模型。它由国内团队发明、开发&#xff0c;并被命名为Mental AI。ChatGPT的目标是通过模拟自然对话的方式&#xff0c;提供高效、智能…...

Linux 常用操作命令

Linux简介及Ubuntu安装 Linux&#xff0c;免费开源&#xff0c;多用户多任务系统。基于Linux有多个版本的衍生。RedHat、Ubuntu、Debian 安装VMware或VirtualBox虚拟机。具体安装步骤&#xff0c;找百度。 再安装Ubuntu。具体安装步骤&#xff0c;找百度。 常用指令 ls  …...

24届近5年重庆邮电大学自动化考研院校分析

今天给大家带来的是重庆邮电大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、重庆邮电大学 学校简介 重庆邮电大学简称"重邮"&#xff0c;坐落于直辖市-重庆市&#xff0c;入选国家"中西部高校基础能力建设工程”、国家“卓越工程师教育培养计划…...

如何对oracle和mysql进行 分区分表

前提&#xff1a;使用自带的分区和分表机制进行操作 oracle,mysql分区分表 分区 分区是一种将一个大的表或索引分割成多个小的部分的技术&#xff0c;每个部分称为一个分区。分区可以提高数据的管理和查询效率&#xff0c;因为可以根据不同的条件对不同的分区进行操作&#x…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...