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

力扣labuladong一刷day30天二叉树

力扣labuladong一刷day30天二叉树

文章目录

      • 力扣labuladong一刷day30天二叉树
      • 一、654. 最大二叉树
      • 二、105. 从前序与中序遍历序列构造二叉树
      • 三、106. 从中序与后序遍历序列构造二叉树
      • 四、889. 根据前序和后序遍历构造二叉树

一、654. 最大二叉树

题目链接:https://leetcode.cn/problems/maximum-binary-tree/
思路:采用分解问题的方法,先构造父节点再构造左右子节点,每次都在指定区间内搜索,找到最大值后构造父节点,再划分左右区间递归。

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return traverse(nums, 0, nums.length - 1);}TreeNode traverse(int[] nums, int left ,int right) {if (left > right) return null;int max = -1, index = -1;for (int i = left; i <= right; i++) {if (nums[i] > max) {max = nums[i];index = i;}}TreeNode root = new TreeNode(max);root.left = traverse(nums, left, index-1);root.right = traverse(nums, index+1, right);return root;}
}

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

题目链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
思路:通过前序和中序构造二叉树,要维护好前序的区间以及中序的区间,先构造父节点再构造左右子节点,父节点是前序区间的left,左右子节点由递归返回。 此外要注意速度,想节省遍历中序数组寻找父节点索引的时间的话,可以使用map预先存储下来。

class Solution {Map<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return create(preorder, inorder, 0, preorder.length-1,0, inorder.length-1);}TreeNode create(int[] preorder, int[] inorder, int left1, int right1, int left2, int right2) {if (left1 > right1 || left2 > right2) return null;int midV = preorder[left1];TreeNode node = new TreeNode(midV);int index = map.get(midV);node.left = create(preorder, inorder, left1+1, left1+index-left2, left2, index-1);node.right = create(preorder, inorder, left1+index-left2+1, right1, index+1, right2);return node;}
}

三、106. 从中序与后序遍历序列构造二叉树

题目链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
思路:本题和上题类似,也是先构造父节点,然后再构造左右子节点,父节点由后续right构造,然后划分中序和后序的区间,递归构造左右子树。

class Solution {Map<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return create(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);}TreeNode create(int[] inorder, int[] postorder, int left1, int right1, int left2, int right2) {if (left1 > right1 || left2 > right2) return null;int midV = postorder[right2];int index = map.get(midV);TreeNode node = new TreeNode(midV);node.left = create(inorder, postorder, left1, index-1, left2, left2+index-left1-1);node.right = create(inorder, postorder, index+1, right1, left2+index-left1, right2-1);return node;}
}

四、889. 根据前序和后序遍历构造二叉树

题目链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
思路:通过前序和后序去构造二叉树,构造的结果不唯一,但方法是一样的,每次使用前序的left做为父节点,left+1做为左孩子的值,然后使用这个去后序中去划分区间,然后在划分前序遍历的区间,之后递归构造即可。

class Solution {Map<Integer, Integer> map = new HashMap<>();public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {for (int i = 0; i < postorder.length; i++) {map.put(postorder[i], i);}return create(preorder, postorder, 0, preorder.length-1, 0, postorder.length-1);}TreeNode create(int[] preorder, int[] postorder, int left1, int right1, int left2, int right2) {if (left1>right1 || left2>right2) return null;if (left1 == right1) return new TreeNode(preorder[left1]);int mid = preorder[left1];int index = map.get(preorder[left1+1]);TreeNode node = new TreeNode(mid);node.left = create(preorder, postorder, left1+1, left1 + index-left2+1, left2,index);node.right = create(preorder, postorder, left1 + index-left2+2, right1,index+1, right2-1);return node;}
}

相关文章:

力扣labuladong一刷day30天二叉树

力扣labuladong一刷day30天二叉树 文章目录 力扣labuladong一刷day30天二叉树一、654. 最大二叉树二、105. 从前序与中序遍历序列构造二叉树三、106. 从中序与后序遍历序列构造二叉树四、889. 根据前序和后序遍历构造二叉树 一、654. 最大二叉树 题目链接&#xff1a;https://…...

【云原生-K8s】检查yaml文件安全配置kubesec部署及使用

基础介绍基础描述特点 部署在线下载百度网盘下载安装 使用官网样例yamlHTTP远程调用安全建议 总结 基础介绍 基础描述 Kubesec 是一个开源项目&#xff0c;旨在为 Kubernetes 提供安全特性。它提供了一组工具和插件&#xff0c;用于保护和管理在 Kubernetes 集群中的工作负载和…...

LeetCode力扣每日一题(Java):20、有效的括号

一、题目 二、解题思路 1、我的思路 我看到题目之后&#xff0c;想着这可能是力扣里唯一一道我能秒杀的题目了 于是一波操作猛如虎写出了如下代码 public boolean isValid(String s) {char[] c s.toCharArray();for(int i0;i<c.length;i){switch (c[i]){case (:if(c[i]…...

解决Flutter运行报错Could not run build/ios/iphoneos/Runner.app

错误场景 更新了IOS的系统版本为最新的17.0, 运行报以下错误 Launching lib/main.dart on iPhone in debug mode... Automatically signing iOS for device deployment using specified development team in Xcode project: GN3DCAF71C Running Xcode build... Xcode build d…...

配置Smart Link主备备份示例

目录 实验拓扑 组网需求 配置思路 配置步骤 1.配置VLAN信息 2.在SwitchA上创建Smart Link备份组&#xff0c;并指定端口角色 3.使能回切功能并设置回切时间 4.使能发送Flush报文功能 5.使能接受Flush报文功能 验证配置结果 实验拓扑 组网需求 如上图所示&#xff0c;…...

03-微服务架构构建之微服务拆分

文章目录 前言一、微服务拆分的原则二、微服务拆分的时机三、微服务拆分的方法总结 前言 微服务架构是将一个单体应用程序拆分为一个个独立且保持松耦合的服务的一种架构方式&#xff0c;每个服务有着独立的数据库并且能独立运行部署。微服务架构的构建过程中&#xff0c;第一…...

Linus:我休假的时候也会带着电脑,否则会感觉很无聊

目录 Linux 内核最新版本动态 关于成为内核维护者 代码好写&#xff0c;人际关系难处理 内核维护者老龄化 内核中 Rust 的使用 关于 AI 的看法 参考 12.5-12.6 日&#xff0c;Linux 基金会组织的开源峰会&#xff08;OSS&#xff0c;Open Source Summit&#xff09;在日…...

快速排序的新用法

普通快排 简介 快速排序是一种高效的排序算法&#xff0c;利用分治的思想进行排序。它的基本原理是在待排序的n个数据中任取一个数据为分区标准&#xff0c;把所有小于该排序码的数据移到左边&#xff0c;把所有大于该排序码的数据移到右边&#xff0c;中间放所选记录&#x…...

利用乔拓云SAAS系统,快速、高效搭建小程序

a-service&#xff0c;软件即服务&#xff09;系统来搭建他们的微信小程序。SAAS系统作为一种创新的软件应用模式&#xff0c;将软件作为一种服务提供给用户&#xff0c;为用户提供了更高效、更便捷的解决方案。本文将探讨为什么越来越多的商家选择使用乔拓云这种SAAS系统搭建小…...

Kubernetes(K8s 1.27.x) 快速上手+实践,无废话纯享版

文章目录 1 基础知识1.1 K8s 有用么&#xff1f;1.2 K8s 是什么&#xff1f;1.3 k8s 部署方式1.4 k8s 环境解析 2 环境部署2.1 基础环境配置2.2 容器环境操作2.3 cri环境操作2.4 harbor仓库操作2.5 k8s集群初始化2.6 k8s环境收尾操作 3 应用部署3.1 应用管理解读3.2 应用部署实…...

非常抱歉的通知

非常感谢有这么多的同志向我提问一些问题&#xff0c;也非常感谢很多的同志可以看我的学习文章&#xff0c;这次大概有四五个月没有上csdn&#xff0c;看到了许多同志的疑问和慰问&#xff0c;我也很感动&#xff0c;但是由于我自己以及其他的原因&#xff0c;我现在打算以考编…...

rust 包模块组织结构

一个包&#xff08;package&#xff09;可以拥有多个二进制单元包及一个可选的库单元包。随着包内代码规模的增长&#xff0c;你还可以将代码拆分到独立的单元包&#xff08;crate&#xff09;中&#xff0c;并将它作为外部依赖进行引用。 RUST提供了一系列的功能来帮助我们管…...

深入浅出:HTTPS单向与双向认证及证书解析20231208

介绍: 网络安全的核心之一是了解和实施HTTPS认证。本文将探讨HTTPS单向认证和双向认证的区别&#xff0c;以及SSL证书和CA证书在这些过程中的作用&#xff0c;并通过Nginx配置实例具体说明。 第一部分&#xff1a;HTTPS单向认证 定义及工作原理&#xff1a;HTTPS单向认证是一…...

水利安全监测方案——基于RTU200的解决方案

引言&#xff1a; 水资源是人类赖以生存的重要基础&#xff0c;对于保障水利系统安全运行以及应对自然灾害起着关键作用。为了实现水利安全监测的目标&#xff0c;我们提出了基于RTU200的解决方案。本方案将结合RTU200的可靠性、灵活性和高效性&#xff0c;为您打造一个全面的…...

安卓开发学习---kotlin版---笔记(一)

Hello word 前言&#xff1a;上次学习安卓&#xff0c;学了Java开发&#xff0c;简单的搭了几个安卓界面。这次要学习Kotlin语言&#xff0c;然后开发安卓&#xff0c;趁着还年轻&#xff0c;学点新东西&#xff0c;坚持~ 未来的你会感谢现在努力的你~ 主要学习资料&#xff1a…...

挑选在线客服系统的七大注意事项

越来越多的企业开始注重客户服务&#xff0c;所以在线客服系统也逐渐成为了电商企业不可或缺的一部分。然而在挑选在线客服系统的过程中&#xff0c;蛮多企业会遇到各种各样的问题&#xff0c;这就导致了最终选择的系统并不适合自己企业的需求。接下来我将提醒大家挑选在线客服…...

剧本杀小程序搭建:打造线上剧本杀新体验

剧本杀是一款以角色扮演为主的游戏&#xff0c;一度成为了年轻人的最喜爱的社交游戏。在剧本杀市场需求下&#xff0c;剧本杀规模也迅速上升。今年第一季度&#xff0c;剧本杀市场规模环比增长47%&#xff0c;市场整体消费水平逐渐呈上升趋势。 随着剧本杀的不断发展&#xff…...

机器学习实战:预测波士顿房价

前言&#xff1a; Hello大家好&#xff0c;我是Dream。 今天来学习一下机器学习中一个非常经典的案例&#xff1a;预测波士顿房价&#xff0c;在此过程中也会补充很多重要的知识点&#xff0c;欢迎大家一起前来探讨学习~ 一、导入数据 在这个项目中&#xff0c;我们利用马萨诸…...

基于个微机器人的开发

简要描述&#xff1a; 下载消息中的动图 请求URL&#xff1a; http://域名/getMsgEmoji 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名必选类型说明…...

程序员学习方法

https://www.zhihu.com/question/24187324 https://www.zhihu.com/question/505750740 windows系统&#xff1a; 如何业余开展 Windows 系统的学习&#xff1f; - 知乎 wifi工作原理&#xff1a; WiFi的工作原理是什么&#xff1f; - 知乎 发...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...