LeetCode刷题---从中序与后序遍历序列构造二叉树

在这里插入图片描述
解题思路:

首先还是定义哈希表将中序遍历的数插入进去,方便后序查阅
创建递归方法buildTreeNew(中序遍历数组,后序遍历数组,左或右子树在中序遍历数组中的起始和终止节点索引,左或右子树在后序遍历数组中的起始和终止节点索引)
后序遍历中最后一个数为二叉树的根节点
递归终止条件lastLeft>lastRight时候返回null

递归过程如下:

首先从后序遍历中找出根节点的值,再把根节点的值当作key查询哈希表得出根节点在中序遍历中的索引位置
创建根节点
递归创建左子树
传入参数中,左子树在中序遍历中的起始索引为中序遍历中第一个数的索引,终止索引为根节点midRoot-1,左子树在后序遍历中的起始索引为后序遍历中第一个数的索引,终止索引为起始索引+左子树的节点个数(通过中序遍历中根节点的索引-1-中序遍历中左子树的起始索引得出)。
递归创建右子树
传入参数中,右子树在中序遍历中的起始索引为midRoot+1,终止索引为midRight,在后序遍历中的起始索引为左子树在后序遍历中的终止索引+1,终止索引为lastRoot-1。
最后返回根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    private Map<Integer,Integer> midMap;

    public TreeNode buildTreeNew(int[] inorder, int[] postorder,int midLeft,int midRight,int lastLeft,int lastRight)
    {
        if(lastLeft>lastRight) return null;
        //获取根节点在后序遍历中索引位置
        int lastRoot=lastRight;
        
        //左子树起始节点在后序遍历中的起始索引
        int startLeft=lastLeft;

        //获取根节点在中序遍历中的索引
        int midRoot=midMap.get(postorder[lastRoot]);
        //根据上一步算出左子树的节点个数
        int leftSize=midRoot-1-midLeft;

        //算出左子树在后序遍历中的终止索引
        int endLeft=startLeft+leftSize;

        //创建根节点
        TreeNode root=new TreeNode(postorder[lastRoot]);

        //递归创建左子树
        root.left=buildTreeNew(inorder,postorder,midLeft,midRoot-1,startLeft,endLeft);

        //递归创建右子树
        root.right=buildTreeNew(inorder,postorder,midRoot+1,midRight,endLeft+1,lastRight-1);

        return root;

    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        midMap =new HashMap<Integer,Integer>();

        int n=inorder.length;

        for(int i=0;i<n;i++)
        {
            midMap.put(inorder[i],i);
        }

        return buildTreeNew(inorder,postorder,0,n-1,0,n-1);
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ThreadLocal从使用到实现原理与源码详解

ThreadLocal概述 ThreadLocal是多线程中对于解决线程安全的一个操作类&#xff0c;它会为每个线程都分配一个独立的线程副本从而解决了变量并发访问冲突的问题。ThreadLocal 同时实现了线程内的资源共享。 案例&#xff1a;使用JDBC操作数据库时&#xff0c;会将每一个线程的…

数据库系统概论(超详解!!!) 第一节 绪论

1.四个基本概念 1.数据&#xff08;Data&#xff09; 数据&#xff08;Data&#xff09;是数据库中存储的基本对象 数据的定义&#xff1a;描述事物的符号记录 数据的种类&#xff1a;数字、文字、图形、图像、音频、视频、学生的档案记录等 数据的含义称为数据的语义&…

第三百六十七回

文章目录 1. 概念介绍2. 方法与细节2.1 获取方法2.2 使用细节 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何获取当前系统语言"相关的内容&#xff0c;本章回中将介绍如何获取时间戳.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在本章…

HCIA-Datacom实验指导手册:5.1 实验一:FTP SFTP TFTP 基础配置实验

HCIA-Datacom实验指导手册&#xff1a;5.1 实验一&#xff1a;FTP 基础配置实验 一、实验介绍&#xff1a;二、实验拓扑&#xff1a;三、实验目的&#xff1a;四、配置步骤&#xff1a;步骤 1 设备基础配置步骤 2 在 Router 上配置 FTP 和SFTP服务器功能及参数步骤 3 配置本地 …

MySQL数据库基础(十五):PyMySQL使用介绍

文章目录 PyMySQL使用介绍 一、为什么要学习PyMySQL 二、安装PyMySQL模块 三、PyMySQL的使用 1、导入 pymysql 包 2、创建连接对象 3、获取游标对象 4、pymysql完成数据的查询操作 5、pymysql完成对数据的增删改 PyMySQL使用介绍 提前安装MySQL数据库&#xff08;可以…

js里面有引用传递吗?

一&#xff1a;什么是引用传递 引用传递是相对于值传递的。那什么是值传递呢&#xff1f;值传递就是在传递过程中再复制一份&#xff0c;然后再赋值给变量&#xff0c;例如&#xff1a; let a 2; let b a;在这个代码中&#xff0c;let b a; 就是一个值传递&#xff0c;首先…

js中浏览器渲染原理

JavaScript&#xff08;JS&#xff09;是一种广泛使用的编程语言&#xff0c;特别是在Web开发中。在浏览器中&#xff0c;JS被用于实现动态网页效果、交互性和用户体验的提升。然而&#xff0c;要理解JS在浏览器中的工作原理&#xff0c;我们首先需要了解浏览器的渲染过程。 浏…

【回顾】蚂蚁链自研TEE技术全项通过国家金融科技认证中心认证

2022年3月&#xff0c;蚂蚁集团自研TEE技术&#xff08;HyperEnclave&#xff09;通过了北京国家金融科技认证中心认证&#xff0c;TEE功能&#xff08;CA与TA交互、数据存储、加密解密算法等&#xff09;、TEE安全&#xff08;硬件安全、系统软件层安全等&#xff09;47个项目…

【51单片机】红外遥控红外遥控电机调速(江科大)

1.红外遥控简介 红外遥控是利用红外光进行通信的设备,由红外LED将调制后的信号发出,由专用的红外接收头进行解调输出 通信方式:单工,异步 红外LED波长:940nm 通信协议标准:NEC标准 2.硬件电路 红外发送部分 IN高电平时&#xff0c;LED不亮&#xff0c;IN低电平时&…

这几个Python内置函数你都知道吗

divmod() divmod() 是一个 Python 内置函数&#xff0c;用于同时返回商和余数。它接受两个参数&#xff0c;第一个参数是被除数&#xff0c;第二个参数是除数&#xff0c;返回一个包含两个值的元组&#xff0c;第一个值是商&#xff0c;第二个值是余数。 示例用法如下&#…

Laravel03 路由到控制器与连接数据库

Laravel03 路由到控制器与连接数据库 1. 路由到控制器2. 连接数据库 1. 路由到控制器 如下图一些简单的逻辑处理可以放在web.php中&#xff0c;也就是路由的闭包函数里面。但是大的项目&#xff0c;我们肯定不能这么写。 为什么保证业务清晰好管理&#xff0c;都应该吧业务逻辑…

设计模式(三)建造者模式

相关文章设计模式系列 1.建造者模式简介 定义 建造者模式&#xff08;builder&#xff09;&#xff0c;将一个复杂对象的构建与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 简介 建造者模式&#xff08;builder&#xff09;是创建一个复杂对象的创建型…

全面介绍HTML的语法!轻松写出网页

文章目录 heading(标题)paragraph(段落)link(超链接)imagemap(映射)table(表格)list(列表)layout(分块)form(表单)更多输入:datalistautocompleteautofocusmultiplenovalidatepatternplaceholderrequired head(首部)titlebaselinkstylemetascriptnoscript iframe HTML&#xff…

【刷题】leetcode 1544.整理字符串

刷题 1544.整理字符串思路一&#xff08;模拟栈速解版&#xff09;思路二 &#xff08;原地算法巧解版&#xff09;思路三&#xff08;C栈版&#xff09; Thanks♪(&#xff65;ω&#xff65;)&#xff89;谢谢阅读&#xff01;&#xff01;&#xff01;下一篇文章见&#xff…

前端学习---- 前端HTML基本元素的介绍

一&#xff1a;显示相关的HTML基础知识 1. 推荐的前端编写工具 2. VScode的html速写规则&#xff08;从a标签开始再用&#xff09; ①、&#xff01;&#xff1a;代表生成html的基本框架元素 ②、html元素&#xff1a;直接书写html,不需要加<>,按回车会自动生成 ③、{}…

linux下执行文件包含^M,将window文件格式内容转为linux格式

查看文件内容 cat -v jvm_options 报错信息 ./bin/install-plugin.sh: /bigdata/opt/s/seatunnelsgg/apache-seatunnel-2.3.4/mvnw: /bin/sh^M: bad interpreter: No such file or directory install connector : connector-selectdb-cloud安装工具 yum install -y dos2uni…

YOLOv9中的“ADown”结构!

ADown结构出炉啦&#xff0c;收藏起来写论文用&#xff01; 1.代码&#xff1a; 代码路径&#xff1a;yolov9-main->models->common.py&#xff0c;代码如下&#xff1a; class ADown(nn.Module):def __init__(self, c1, c2): # ch_in, ch_out, shortcut, kernels, gro…

Z 字形变换

题目链接 Z 字形变换 题目描述 注意点 s 由英文字母&#xff08;小写和大写&#xff09;、‘,’ 和 ‘.’ 组成1 < numRows < 1000 解答思路 方法一是模拟整个Z字形变换思路&#xff0c;使用一个二维数组存储变换后的矩阵&#xff0c;首先需要确定这个矩阵的行数row和…

PDF控件Spire.PDF for .NET【安全】演示:从加密的 PDF 文档中删除密码

Spire.PDF for .NET 是一款独立 PDF 控件&#xff0c;用于 .NET 程序中创建、编辑和操作 PDF 文档。使用 Spire.PDF 类库&#xff0c;开发人员可以新建一个 PDF 文档或者对现有的 PDF 文档进行处理&#xff0c;且无需安装 Adobe Acrobat。 E-iceblue 功能类库Spire 系列文档处…

C++11右值引用

文章目录 左值左值引用 右值右值引用左值引用和右值引用左值引用和右值引用总结 右值引用使用场景和意义左值引用的使用场景左值引用的缺点右值引用移动构造移动赋值 右值引用的其他使用场景 万能引用完美转发完美转发的实际应用场景 C11之前就有了引用的语法&#xff0c;而C11…