LeetCode 热题 100(七):105. 从前序与中序遍历序列构造二叉树、14. 二叉树展开为链表

题目一:

105. 从前序与中序遍历序列构造二叉树icon-default.png?t=N6B9https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路:依据前序遍历的根左右和中序遍历的左根右, 且根左长度=左根

代码:

class Solution {HashMap<Integer, Integer> map ;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();int n = preorder.length;for (int i = 0; i < n; i++)map.put(inorder[i], i);return mybuildTree(preorder, 0, n - 1, inorder, 0, n - 1);}private TreeNode mybuildTree(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {if (preBegin > preEnd || inBegin > inEnd) return null;// 前序遍历的头结点一定是根结点  比如pre_rootIndex = 0int pre_rootIndex = preBegin;// 根据根结点值获取到它在中序遍历的索引值  preorder[pre_rootIndex就是当前根节点值int inorder_rootIndex = map.get(preorder[pre_rootIndex]);// 构建根结点TreeNode root = new TreeNode(preorder[pre_rootIndex]);// 截取长度  得到左子树的元素个数int len = inorder_rootIndex - inBegin;// 注意起始,  前序遍历左子树的开始节点是根节点的下一个,结束节点是加上左子树长度, 中序遍历的好理解root.left = mybuildTree(preorder, preBegin + 1, preBegin + len, inorder, inBegin, inorder_rootIndex - 1);// 前序遍历右子树就是(根+左子树)的长度即原先起始+1+len  root.right = mybuildTree(preorder, preBegin + 1 + len, preEnd, inorder, inorder_rootIndex + 1, inEnd);return root;}
}

题目二:

14. 二叉树展开为链表icon-default.png?t=N6B9https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

思路:前序遍历

代码:

class Solution {public void flatten(TreeNode root) {List<TreeNode> list = new ArrayList<>();preorder(root, list);int size = list.size();for (int i = 1 ; i < size; i++) {TreeNode pre = list.get(i - 1), cur = list.get(i);// 保证父节点的左子树为null  右子树为下一个索引为i的值pre.left = null;pre.right = cur;}}// 前序遍历private void preorder(TreeNode root, List<TreeNode> list){if (root == null) return;list.add(root);preorder(root.left, list);preorder(root.right, list);} 
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/110229.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【已解决】pycharm突然双击无法打开,重启电脑也不管用

1.问题&#xff1a; pycharm突然双击无法打开&#xff0c;重启电脑也不管用 2.解决 2.1 方法一&#xff08;修改Roaming&#xff09; 1.找到C盘对应路径下的pycharm版本 2. 用记事本打开文件类型为VMOPTIONS文件 3. 修改或删除最后一行的映射路径 4.保存退出 2.2 方法二…

二级MySQL(二)——编程语言,函数

SQL语言又称为【结构化查询语言】 请使用FLOOR&#xff08;x&#xff09;函数求小于或等于5.6的最大整数 请使用TRUNCATE&#xff08;x&#xff0c;y&#xff09;函数将数字1.98752895保留到小数点后4位 请使用UPPER&#xff08;&#xff09;函数将字符串‘welcome’转化为大写…

Linux重置ROOT密码(CentOS)

解释说明 在CentOS中重置root密码通常需要进入单用户模式&#xff0c;这是一个没有密码限制的特殊模式&#xff0c;允许您以root权限登录系统并更改密码。 重启系统 如果您无法登录到系统&#xff0c;可以通过重启系统来开始这个过程。您可以使用虚拟机控制台、物理服务器控制台…

Leetcode 191.位1的个数

编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 1 的个数&#xff08;也被称为汉明重量&#xff09;。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff08;如 Java&#xff09;中…

java+springboot+mysql农业园区管理系统

项目介绍&#xff1a; 使用javaspringbootmysql开发的农业园区管理系统&#xff0c;系统包含超级管理员、管理员、用户角色&#xff0c;功能如下&#xff1a; 超级管理员&#xff1a;管理员管理&#xff1b;用户管理&#xff1b;土地管理&#xff08;租赁&#xff09;&#x…

语言模型(language model)

文章目录 引言1. 什么是语言模型2. 语言模型的主要用途2.1 言模型-语音识别2.2 语言模型-手写识别2.3 语言模型-输入法 3. 语言模型的分类4. N-gram语言模型4.1 N-gram语言模型-平滑方法4.2 ngram代码4.3 语言模型的评价指标4.4 两类语言模型的对比 5. 神经网络语言模型6. 语言…

RabbitMQ的镜像队列

镜像队列 如果 RabbitMQ 集群中只有一个 Broker 节点&#xff0c;那么该节点的失效将导致整体服务的临时性不可用&#xff0c;并且也可能会导致消息的丢失。可以将所有消息都设置为持久化&#xff0c;并且对应队列的durable 属性也设置为 true &#xff0c;但是这样仍然无法…

基于java swing和mysql实现的汽车租赁管理系统(源码+数据库+文档+运行指导视频)

一、项目简介 本项目是一套基于java swing和mysql实现的汽车租赁管理系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、项目文档、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经…

计算机竞赛 基于YOLO实现的口罩佩戴检测 - python opemcv 深度学习

文章目录 0 前言1 课题介绍2 算法原理2.1 算法简介2.2 网络架构 3 关键代码4 数据集4.1 安装4.2 打开4.3 选择yolo标注格式4.4 打标签4.5 保存 5 训练6 实现效果6.1 pyqt实现简单GUI6.3 视频识别效果6.4 摄像头实时识别 7 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xf…

打架斗殴监测识别算法 yolov8

打架斗殴监测识别算法采用yolov8先进的图像处理和机器学习算法框架模型&#xff0c;打架斗殴监测识别算法能够自动识别和分析出打架斗殴的行为特征。一旦系统检测到打架斗殴行为&#xff0c;将自动触发告警。YOLO的结构非常简单&#xff0c;就是单纯的卷积、池化最后加了两层全…

抢先体验|乐鑫推出 ESP32-S3-BOX-3 新一代开源 AIoT 开发套件

乐鑫科技 (688018.SH) 非常高兴地宣布其开发套件阵容的最新成员 ESP32-S3-BOX-3。这款完全开源的 AIoT 应用开发套件搭载乐鑫高性能 ESP32-S3 AI SoC&#xff0c;旨在突破传统开发板&#xff0c;成为新一代开发工具的引领者。 【乐鑫新品抢先体验】ESP32-S3-BOX-3 新一代开源 A…

文件上传漏洞之条件竞争

这里拿upload-labs的第18关做演示 首先先看代码 $is_upload false; $msg null;if(isset($_POST[submit])){$ext_arr array(jpg,png,gif);$file_name $_FILES[upload_file][name];$temp_file $_FILES[upload_file][tmp_name];$file_ext substr($file_name,strrpos($file_…

AES+base64+远程加载----ConsoleApplication811项目

ConsoleApplication9.cpp // ConsoleApplication9.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //#include <iostream> #include <Windows.h> #include <wininet.h> #include "base64.h" #include "AES.h" …

【Rust】Rust学习 第十九章高级特征

现在我们已经学习了 Rust 编程语言中最常用的部分。在第二十章开始另一个新项目之前&#xff0c;让我们聊聊一些总有一天你会遇上的部分内容。你可以将本章作为不经意间遇到未知的内容时的参考。本章将要学习的功能在一些非常特定的场景下很有用处。虽然很少会碰到它们&#xf…

Redis进阶 - Lua语法

原文首更地址&#xff0c;阅读效果更佳&#xff01; Redis进阶 - Lua语法 | CoderMast编程桅杆https://www.codermast.com/database/redis/redis-advance-lua-language.html 初识 Lua Lua 是一种轻量小巧的脚本语言&#xff0c;用标准的 C 语言编写并以源代码形式开放&#…

闲人闲谈PS之四十六——网络生产全流程

惯例闲话&#xff1a;下半年已开始块行情似乎又是一波大涨&#xff0c;很多朋友委托我介绍PS顾问&#xff0c;很多朋友已经上了能源系统项目&#xff0c;这就造成装备制造的PS又是极度紧缺&#xff0c;rate也还可以&#xff0c;搞的自己也有点心痒痒。这种逆势大涨&#xff0c;…

Django(8)-静态资源引用CSS和图片

除了服务端生成的 HTML 以外&#xff0c;网络应用通常需要一些额外的文件——比如图片&#xff0c;脚本和样式表——来帮助渲染网络页面。在 Django 中&#xff0c;我们把这些文件统称为“静态文件”。 我们使用static文件来存放静态资源&#xff0c;django会在每个 INSTALLED…

ReoGrid.NET集成到winfrom

ReoGrid一个支持excel操作的控件,支持集成到任何winfrom项目内。 先看效果图: 如何使用&#xff1a; 使用ReoGrid自带excel模版设计工具先设计一个模版,设计器如下&#xff1a; 具体例子看官方文档 代码示例如下&#xff1a; var sheet reoGridControl1.CurrentWorksheet; …

从C语言到C++_34(C++11_下)可变参数+ lambda+function+bind+笔试题

目录 1. 可变参数模板 1.1 展开参数包 1.1.1 递归函数方式展开 1.1.2 逗号表达式展开 1.2 emplace相关接口 2. lambda表达式&#xff08;匿名函数&#xff09; 2.1 C11之前函数的缺陷 2.2 lambda表达式语法 2.3 函数对象与lambda表达式 3. 包装器 3.1 function包装器…

华为云服务器前后端分离项目打包上传及nginx配置

目录 1、Spring Boot项目打包 2、后端上传到云服务器 3、前端打包 1&#xff09;前端请求路径修改 2&#xff09;打包上传 4、下载nginx 1&#xff09;添加源 2&#xff09;安装Nginx 3&#xff09;查看nginx安装目录和版本 4&#xff09;启动 重启nginx命令 5&#…