【算法】leetcode 105 从前序与中序遍历序列构造二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制:

0 <= 节点个数 <= 5000

解答

#include <iostream>
#include <unordered_map>
#include <vector>using namespace std;struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for (int i = 0; i < inorder.size(); i++){// 用中序遍历数组建立 值-下标 的映射value_index[inorder[i]] = i;}return recursive(preorder,0, 0, inorder.size() - 1);}TreeNode *recursive(vector<int>& pre,int pre_root, int in_left, int in_right){if (in_left > in_right) return nullptr;// 将对应的 val 赋给 node 节点TreeNode *node = new TreeNode(pre[pre_root]);int in_root = value_index[pre[pre_root]];node->left = recursive(pre,pre_root + 1, in_left, in_root - 1);node->right = recursive(pre,pre_root + in_root - in_left + 1, in_root + 1, in_right);return node;}
private:unordered_map<int, int> value_index;
};

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

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

相关文章

SpringBoot自定义消息总线

一、前言 在现代的分布式系统中&#xff0c;消息传递已成为一个非常流行的模式。它使得系统内的不同部分可以松耦合地通信&#xff0c;从而实现更高效、更可靠的应用程序。本博客将介绍SpringBoot如何提供简单易用的消息传递机制&#xff0c;并展示如何自定义消息总线以满足特定…

kafka详解二

kafka详解二 1、 offset 1.1 offset介绍 老版本 Consumer 的位移管理是依托于 Apache ZooKeeper 的&#xff0c;它会自动或手动地将位移数据提交到 ZooKeeper 中保存。当 Consumer 重启后&#xff0c;它能自动从 ZooKeeper 中读取位移数据&#xff0c;从而在上次消费截止的地…

【探索SpringCloud】服务发现-Nacos服务端数据结构和模型

前言 上一文中&#xff0c;我们从官方的图示了解到Nacos的服务数据结构。但我关心的是&#xff0c;Nacos2.x不是重构了吗&#xff1f;怎么还是这种数据结构&#xff1f;我推测&#xff0c;必然是为了对Nacos1.x的兼容&#xff0c;实际存储应该不是这样的。于是&#xff0c;沿着…

vue的第2篇 第一个vue程序

一 环境的搭建 1.1常见前端开发ide 1.2 安装vs.code 1.下载地址&#xff1a;Visual Studio Code - Code Editing. Redefined 2.进行安装 1.2.1 vscode的中文插件安装 1.在搜索框输入“chinese” 2.安装完成重启&#xff0c;如下变成中文 1.2.2 修改工作区的颜色 选中[浅色]…

opencv 提取选中区域内指定hsv颜色的水印

基于《QT 插件化图像算法研究平台》做的功能插件。提取选中区域内指定hsv颜色的水印。 《QT 插件化图像算法研究平台》有个HSV COLOR PICK功能&#xff0c;可以很直观、方便地分析出水印 的hsv颜色&#xff0c;比如, 蓝色&#xff1a;100,180,0,255,100,255。 然后利用 opencv …

Django(10)-项目实战-对发布会管理系统进行测试并获取测试覆盖率

在发布会签到系统中使用django开发了发布会签到系统&#xff0c; 本文对该系统进行测试。 django.test django.test是Django框架中的一个模块&#xff0c;提供了用于编写和运行测试的工具和类。 django.test模块包含了一些用于测试的类和函数&#xff0c;如&#xff1a; Tes…

每日一题 1372二叉树中的最长交错路径

题目 给你一棵以 root 为根的二叉树&#xff0c;二叉树中的交错路径定义如下&#xff1a; 选择二叉树中 任意 节点和一个方向&#xff08;左或者右&#xff09;。如果前进方向为右&#xff0c;那么移动到当前节点的的右子节点&#xff0c;否则移动到它的左子节点。改变前进方…

vscode 清除全部的console.log

在放页面的大文件夹view上面右键点击在文件夹中查找 console.log.*$ 注意&#xff1a;要选择使用正则匹配 替换为 " " (空字符串)

跨模态可信感知

文章目录 跨模态可信感知综述摘要引言跨协议通信模式PCP网络架构 跨模态可信感知跨模态可信感知的概念跨模态可信感知的热点研究场景目前存在的挑战可能改进的方案 参考文献 跨模态可信感知综述 摘要 随着人工智能相关理论和技术的崛起&#xff0c;通信和感知领域的研究引入了…

ELK日志收集系统(四十九)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 前言 一、概述 二、组件 1. elasticsearch 2. logstash 2.1 工作过程 2.2 INPUT 2.3 FILETER 2.4 OUTPUTS 3. kibana 三、架构类型 3.1 ELK 3.2 ELKK 3.3 ELFK 3.5 EF…

VScode远程连接主机

一、前期准备 1、Windows安装VSCode&#xff1b; 2、在VSCode中安装PHP Debug插件&#xff1b; 3、安装好Docker 4、在容器中安装Xdebug ①写一个展现phpinfo的php文件 <?php phpinfo(); ?>②在浏览器上打开该文件 ③复制所有信息丢到Xdebug: Installation instr…

【C进阶】深度剖析数据在内存中的存储

目录 一、数据类型的介绍 1.类型的意义&#xff1a; 2.类型的基本分类 二、整形在内存中的存储 1.原码 反码 补码 2.大小端介绍 3.练习 三、浮点型在内存中的存储 1.一个例子 2.浮点数存储规则 一、数据类型的介绍 前面我们已经学习了基本的内置类型以及他们所占存储…

封装(个人学习笔记黑马学习)

1、格式 #include <iostream> using namespace std;const double PI 3.14;//设计一个圆类&#xff0c;求圆的周长 class Circle {//访问权限//公共权限 public://属性//半径int m_r;//行为//获取圆的周长double calculateZC() {return 2 * PI * m_r;} };int main() {//通…

Linux 学习笔记(1)——系统基本配置与开关机命令

目录 0、起步 0-1&#xff09;命令使用指引 0-2&#xff09;查看历史的命令记录 0-3&#xff09;清空窗口内容 0-4&#xff09;获取本机的内网 IP 地址 0-5&#xff09;获取本机的公网ip地址 0-6&#xff09;在window的命令行窗口中远程连接linux 0-7&#xff09;修改系…

VScode 国内下载源 以及 nvm版本控制器下载与使用

VScode 国内下载源 进入官网 https://code.visualstudio.com/ 点击下载 复制下载链接到新的浏览器标签 将地址中的/stable前的az764295.vo.msecnd.net换成vscode.cdn.azure.cn&#xff0c;再回车就会直接在下载列表啦。 参考大神博客 2.使用nvm 对 node 和npm进行版本控制…

ARM编程模型-内存空间和数据

ARM属于RISC体系&#xff0c;许多指令单周期指令&#xff0c;是32位读取/存储架构&#xff0c;对内存访问是32位&#xff0c;Load and store的架构&#xff0c;只有寄存器对内存&#xff0c;不能内存对内存存储&#xff0c;CPU通过寄存器对内存进行读写操作。 ARM的寻址空间是线…

go Session的实现(一)

〇、前言 众所周知&#xff0c;http协议是无状态的&#xff0c;这对于服务器确认是哪一个客户端在发请求是不可能的&#xff0c;因此为了能确认到&#xff0c;通常方法是让客户端发送请求时带上身份信息。容易想到的方法就是客户端在提交信息时&#xff0c;带上自己的账户和密…

17.看楼房

目录 Description Input Output Notes 思路 注意事项 C完整代码&#xff08;含详细注释&#xff09; Description 小张在暑假时间进行了暑期社会调查。调查的内容是楼房的颜色如何影响人们的心情。于是他找到了一个楼房从左到右排成一排的小区&#xff0c;这个小区一共有…

51单片机项目(7)——基于51单片机的温湿度测量仿真

本次做的设计&#xff0c;是利用DHT11传感器&#xff0c;测量环境的温度以及湿度&#xff0c;同时具备温度报警的功能&#xff1a;利用两个按键&#xff0c;设置温度阈值的加和减&#xff0c;当所测温度大于温度阈值的时候&#xff0c;蜂鸣器就会响起&#xff0c;进行报警提示。…

安卓 tcp 客户端

安卓 tcp 客户端 Server:8888 是Qt 写的Tcp 服务器 ip 是 192.168.2.103 port是8888 安卓手机运行 kotlin 语法的Tcp Client &#xff0c;连接&#xff0c;收发数据 效果如下图 Tcpclient package com.example.myapplicationimport android.os.Handler import android.os.Loo…