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

从前序与中序遍历序列构造二叉树,从中序与后序遍历序列构造二叉树

目录

  • 从前序与中序遍历序列构造二叉树
  • 从中序与后序遍历序列构造二叉树

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


题目链接

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

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

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

首先我们应该明白,
前序遍历就是,先遍历根节点,然后遍历左子树,最后遍历右子树
中序遍历就是,先遍历左子树,然后遍历根节点,最后遍历右子树
后续遍历就是,先遍历左子树,然后遍历右子树,最后遍历根节点

首先我们先试着用前序与中序遍历序列构造一棵二叉树
在这里插入图片描述


给出前序遍历数列 preorder 和 中序遍历数列 inorder
我们知道前序遍历二叉树必然先走根节点,所以我们可知preorder序列中的第一个数字3即为二叉树的根节点,中序遍历数列中,左子树必然先于右子树遍历,所以我们可知,在中序遍历数列inorder中的使用根节点将inorder划分为三个区间,(左子树)根(右子树),根节点3左边的元素为左子树,3右边的元素为右子树

在这里插入图片描述

现在3的左子树为空,右子树(15,20,7)继续使用相同方法构造二叉树
在这里插入图片描述

代码:

采用递归调用,分解子问题的方法

class Solution {
public:TreeNode* build(vector<int>& preorder,vector<int>& inorder,int& prev,int inbegin,int inend){	//perorder 前序遍历序列,inorder 中序遍历序列,prev 指向前序遍历数列下标if(inbegin>inend)return NULL;//当前的根节点TreeNode* root=new TreeNode(preorder[prev]);int rooti=inbegin; //用来查找根节点在数组中的下班位置while(rooti<inend){if(inorder[rooti]==preorder[prev])break;rooti++;}prev++;  //每次使用完prev需往后走,prev指的是数组前序遍历中用来判断根节点的//划分区间,(左子树,根)根(根,右子树)// (inbegin,rooti-1)rooti(rooti+1,inend)//函数递归继续构造二叉树的左右节点root->left=build(preorder,inorder,prev,inbegin,rooti-1); root->right=build(preorder,inorder,prev,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;TreeNode* root=build(preorder,inorder,i,0,inorder.size()-1);return root;}
};

从中序与后序遍历序列构造二叉树


题目链接

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

实例1:

在这里插入图片描述

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

使用中序与后序遍历序列构造二叉树 思路根前序与中序序列构造二叉树相似

在这里插入图片描述
给出二叉树的中序遍历inorder 和 后续遍历 postorder

我们知道后续遍历二叉树,根节点最后遍历,所以我们可知postorder序列中的最后一个元素3即为二叉树的根节点,中序遍历数列中,左子树优于根先遍历,右子树后于根遍历,所以我们可以根据这两个条件将inorder序列划分为三个区间,(左子树)根(右子树),根节点3左边的元素为左子树,3右边的元素为右子树
在这里插入图片描述

3的左子树序列只剩一个,即为3的左节点,右子树序列还有三个元素,需要继续划分,重复上述过程
在这里插入图片描述

代码:

class Solution {
public:TreeNode* build(vector<int>& inorder, vector<int>& postorder,int& prev,int inbegin,int inend){if(inbegin>inend)return NULL;TreeNode* root=new TreeNode(postorder[prev]);int rooti=inbegin;while(rooti<inend){if(postorder[prev]==inorder[rooti])break;rooti++;}prev--;//  (左,根)根(根,右)//先构造右子树,再构造左子树root->right=build(inorder,postorder,prev,rooti+1,inend);root->left=build(inorder,postorder,prev,inbegin,rooti-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;TreeNode* root=build(inorder,postorder,i,0,postorder.size()-1);return root;}
};

相关文章:

从前序与中序遍历序列构造二叉树,从中序与后序遍历序列构造二叉树

目录 从前序与中序遍历序列构造二叉树从中序与后序遍历序列构造二叉树 从前序与中序遍历序列构造二叉树 题目链接 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返…...

【JS常见数据结构】

JS数据结构 前言数组JavaScript 中数组的常见操作&#xff1a;1. 创建数组&#xff1a;2. 访问数组元素&#xff1a;3. 插入元素&#xff1a;4. 删除元素&#xff1a;5. 查询元素&#xff1a; 链表单向链表双向链表循环链表 栈队列树二叉树示例 图图的定义图的分类图的表示方法…...

算法基础之插入排序

1、插入排序基本思想 插入排序的工作原理是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。插入排序在实现上&#xff0c;通常采用in-place排序&#xff08;即只需用到O(1)的额外空间的排序&#xff09;&a…...

InfoQ 分享

...

Jupyter Notebook 遇上 NebulaGraph,可视化探索图数据库

在之前的《手把手教你用 NebulaGraph AI 全家桶跑图算法》中&#xff0c;除了介绍了 ngai 这个小工具之外&#xff0c;还提到了一件事有了 Jupyter Notebook 插件: https://github.com/wey-gu/ipython-ngql&#xff0c;可以更便捷地操作 NebulaGraph。 本文就手把手教你咋在 J…...

人类与机器的分类不同

分类能力也是智能的重要标识之一。通过分类&#xff0c;我们可以将事物或概念进行归类和组织&#xff0c;从而更好地理解和处理信息。分类在人类认知和智能发展中起到了重要的作用&#xff0c;它有助于我们对世界进行认知、记忆、推理和决策。在机器智能领域&#xff0c;分类同…...

WEB安全-SQL注入,CSRF跨站伪造,OXX跨站脚本

SQL 注入攻击 SQL 注入是一种网络攻击手段&#xff0c;攻击者通过在 Web 应用程序的输入字段中插入恶意 SQL 代码&#xff0c;试图访问、篡改或删除数据库中的数据。这种攻击通常发生在应用程序未对用户输入进行充分验证或过滤的情况下。 举个例子&#xff0c;例如&#xff0c;…...

【HDFS】客户端读某个块时,如何对块的各个副本进行网络距离排序?

本文包含如下内容: ① 通过图解+源码分析/A1/B1/node1和 /A1/B2/node2 这两个节点的网络距离怎么算出来的 ② 客户端读文件时,副本的优先级。(怎么排序的,排序规则都有哪些?) ③ 我们集群发现的一个问题。 客户端读时,通过调用getBlockLocations RPC 获取文件的各个块。…...

【数字化处理】仿生假体控制中肌电信号的数字化处理研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

谷歌推出Flax:JAX的神经网络库

在优化理论中&#xff0c;损失或成本函数测量拟合或预测值与实际值之间的距离。对于大多数机器学习模型&#xff0c;提高性能意味着最小化损失函数。 但对于深度神经网络&#xff0c;执行梯度下降以最小化每个参数的损失函数可能会消耗大量资源。传统方法包括手动推导和编码&a…...

PDF换行的难度,谁能解决?

换行的时候确认不了长度&#xff1a; import java.awt.*;public class Test {public static void main(String[] args) {String str1 "淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘淘";String str2 "AAAAAAAAAAAAAAAAAAAAAAAAA…...

山东布谷科技直播程序源码使用Redis进行服务器横向扩展

当今&#xff0c;直播程序源码平台作为新媒体时代主流&#xff0c;受到了世界各地人民的喜爱&#xff0c;这也使得直播程序源码平台用户数量的庞大&#xff0c;也难免会出现大量用户同时访问服务器&#xff0c;使服务器过载的情况&#xff0c;当服务器承受不住的时候&#xff0…...

symfony3.4中根据角色不同跳转不同页面

在Symfony 3.4中&#xff0c;可以使用安全组件来实现控制不同角色跳转到不同页面的功能。 首先&#xff0c;确保你已经安装了Symfony的安全组件&#xff0c;并配置了安全相关的配置文件。这些文件通常是 security.yml 和 security.yml。 在配置文件中&#xff0c;你可以定义不…...

Dockerfile部署golang,docker-compose

使用go镜像打包&#xff0c;运行在容器内 redis和mysql用外部的 项目目录结构 w1go项目&#xff1a; Dockerfile # 这种方式是docker项目加上 本地的mysql和redis环境 # go打包的容器 FROM golang:alpine AS builder# 为我们镜像设置一些必要的环境变量 ENV GO111MODULEon …...

什么是Linux,如何在Windows操作系统下搭建Linux环境,远程连接Linux系统

文章目录 什么是LinuxLinux的诞生及发展为什么要学习LinuxLinux内核Linux发行版什么是虚拟机如何在VMware虚拟机中搭建Linux系统环境远程连接 Linux 系统Linux 帮助网站 什么是Linux Linux是一套免费使用和自由传播的类Unix操作系统&#xff0c;是一个基于POSIX和UNIX的多用户…...

Ubuntu下RabbitMQ安装与简单使用

一&#xff1a;RabbitMQ基本安装 1.更新依赖包(提前更新依赖包避免出现报错) sudo apt-get update 2.由于rabbitMq使用erlang语言开发&#xff0c;在安装rabbitMq之前需要安装erlang sudo apt-get install erlang 3.查看erlang是否安装成功 sudo erl 安装成功会出现下面的提示…...

力扣62.不同路径(动态规划)

/*** 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。* 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xff09;。* 问总共有多少条不同的路径&#xff1f; *…...

TypeScript 泛型的概念和基本使用

什么是TypeScript 泛型&#xff1f; 在定义函数&#xff0c;接口&#xff0c;类的时候不能预先确定使用的数据类型&#xff0c;而是在调用使用这些函数&#xff0c;接口&#xff0c;类的时候才能确定的数据类型&#xff1b; 1&#xff0c;单个泛型的参数 例如通过使用any这种…...

redis的事务和watch机制

这里写目录标题 第一章、redis事务和watch机制1.1&#xff09;redis事务&#xff0c;事务的三大命令语法&#xff1a;开启事务 multi语法&#xff1a;执行事务 exec语法&#xff1a;取消事务 discard 1.2&#xff09;redis事务的错误和回滚的情况1.3&#xff09;watch机制语法&…...

objectMapper.getTypeFactory().constructParametricType 方法的作用和使用

在使用 Jackson 库进行 JSON 数据的序列化和反序列化时&#xff0c;经常会使用到 ObjectMapper 类。其中&#xff0c;objectMapper.getTypeFactory().constructParametricType 方法用于构造泛型类型。 具体作用和使用如下&#xff1a; 作用&#xff1a; 构造泛型类型&#x…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...