当前位置: 首页 > 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…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

AWS vs 阿里云:功能、服务与性能对比指南

在云计算领域&#xff0c;Amazon Web Services (AWS) 和阿里云 (Alibaba Cloud) 是全球领先的提供商&#xff0c;各自在功能范围、服务生态系统、性能表现和适用场景上具有独特优势。基于提供的引用[1]-[5]&#xff0c;我将从功能、服务和性能三个方面进行结构化对比分析&#…...

spring boot使用HttpServletResponse实现sse后端流式输出消息

1.以前只是看过SSE的相关文章&#xff0c;没有具体实践&#xff0c;这次接入AI大模型使用到了流式输出&#xff0c;涉及到给前端流式返回&#xff0c;所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...

C#最佳实践:为何优先使用as或is而非强制转换

C#最佳实践&#xff1a;为何优先使用as或is而非强制转换 在 C# 的编程世界里&#xff0c;类型转换是我们经常会遇到的操作。就像在现实生活中&#xff0c;我们可能需要把不同形状的物品重新整理归类一样&#xff0c;在代码里&#xff0c;我们也常常需要将一个数据类型转换为另…...