LeetCode刷题之105. 从前序与中序遍历序列构造二叉树

文章目录

  • 1.题目描述
  • 2. 分析
    • 2.1 前序遍历
      • 2.1.1 什么是前序遍历?
      • 2.1.2 前序遍历有什么特点?
    • 2.2 中序遍历
      • 2.2.1 什么是中序遍历
      • 2.2.2 中序遍历有什么特点?
    • 2.3 后序遍历
      • 2.3.1 什么是后序遍历?
      • 2.3.2 特点
    • 2.4 总结
  • 3. 解法

1.题目描述

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

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

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

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

2. 分析

对于一颗普通的二叉树而言(如上图),我们知道的信息包括 根节点,左子树,右子树。遍历,就是每个节点都被访问了。

要解决这个问题,那么要明白下面的问题:

  • 什么是前序遍历?
  • 是什么中序遍历?
  • 以及他们都有什么特点?

2.1 前序遍历

2.1.1 什么是前序遍历?

二叉树的前序遍历是一种常见的树遍历方法,用于按照根-左子树-右子树的顺序遍历二叉树的节点。
具体的前序遍历步骤如下:

    1. 访问当前节点:首先访问二叉树的根节点。
    1. 递归遍历左子树:如果当前节点有左子树,就递归地对左子树进行前序遍历,即重复步骤1和步骤2。
    1. 递归遍历右子树:如果当前节点有右子树,就递归地对右子树进行前序遍历,即重复步骤1和步骤2。

以下是一个示例二叉树的前序遍历序列:1-2-4-5-3。

    1
   / \
  2   3
 / \
4   5

按照前序遍历的顺序,首先访问根节点1,然后遍历左子树,访问节点2,再遍历左子树,访问节点4,没有左子树后回溯到节点2,遍历右子树,访问节点5。最后回溯到根节点1后,遍历右子树,访问节点3。因此,前序遍历序列为1-2-4-5-3。

2.1.2 前序遍历有什么特点?

从前序遍历的结果可以看出:

    1. 根节点在首位。
    1. 后面紧跟着的是左子树和右子树。
    1. 子树本身也符合根节点在首位,后面紧跟左右子树的特点。

2.2 中序遍历

2.2.1 什么是中序遍历

有了前门前序遍历的介绍,中序遍历就简单了。中序遍历就是先左节点-再根节点-最后右节点的方式遍历二叉树。

以下是一个示例二叉树的中序遍历序列:4-2-5-1-3。

    1
   / \
  2   3
 / \
4   5

按照中序遍历的顺序,首先遍历左子树,访问节点4,然后回溯到节点2,访问节点2本身,再遍历右子树,访问节点5。回溯到根节点1后,访问根节点1,再遍历右子树,访问节点3。因此,中序遍历序列为4-2-5-1-3。

2.2.2 中序遍历有什么特点?

    1. 根节点的前面是左子树
    1. 根节点的右面是右子树

2.3 后序遍历

2.3.1 什么是后序遍历?

后序遍历,那就是按左节点-右节点-根节点的方式遍历二叉树。
以下是一个示例二叉树的后序遍历序列:4-5-2-3-1。

    1
   / \
  2   3
 / \
4   5

按照后序遍历的顺序,首先遍历左子树,访问节点4,然后遍历右子树,访问节点5。回溯到根节点2后,访问节点2本身,然后遍历右子树,访问节点3。最后回溯到根节点1后,访问根节点1。因此,后序遍历序列为4-5-2-3-1。

2.3.2 特点

  • 根节点在最后

2.4 总结

一颗确定的二叉树,有确定的前、中、后序遍历,但是单一的一个前中后序遍历,并不能确定一颗二叉树。要想确定这颗二叉树,那就需要两个遍历序列。

这里我们有了前序和中序遍历,那就可以根据特点推出完整二叉树:

前序遍历: 【3, 9, 20, 15, 7】
中序遍历: 【9, 3, 15, 20, 7】

首先根据前序遍历找到跟节点3, 那么中序遍历中根节点3前门的所有节点都是左子树节点。
由于前序遍历后面紧跟着左子树和右子树节点,根据数量,我们也可以分出前序遍历里左右子树的节点。
然后递归调用构建完整二叉树。

3. 解法

/**
 * 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 {

    Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<>();

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

        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderLeftIndex, int preorderRightIndex, int inorderLeftIndex, int inorderRightIndex) {
        if (preorderLeftIndex > preorderRightIndex) {
            return null;
        }

        int preorderRootIndex = preorderLeftIndex;
        int inorderRootIndex = indexMap.get(preorder[preorderRootIndex]);

        TreeNode root = new TreeNode(preorder[preorderRootIndex]);

        int leftSubtreeSize = inorderRootIndex - inorderLeftIndex;
        root.left = myBuildTree(preorder, inorder, preorderLeftIndex + 1, preorderLeftIndex + leftSubtreeSize, inorderLeftIndex, inorderRootIndex - 1);

        root.right = myBuildTree(preorder, inorder, preorderLeftIndex + leftSubtreeSize + 1, preorderRightIndex, inorderRootIndex + 1, inorderRightIndex);

        return root;

    }
}

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

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

相关文章

【算法基础】选择排序与冒泡排序的思想与实现

文章目录 1. 选择排序1.1 思想1.2 实现 2. 冒泡排序2.1 思想2.2 实现 1. 选择排序 1.1 思想 选择排序的思想很简单&#xff0c;如上图所示。在每一次遍历子数组的过程中&#xff0c;选择最小的和子数组的第一位交换。子数组的选择从一开始的整个数组&#xff0c;到后面范围逐渐…

Vue2(十四):路由的使用及注意点、嵌套路由、路由的query和params参数、props配置

一、路由的简介 vue-rooter&#xff1a;是vue的一个插件库&#xff0c;专门用来实现SPA应用 1.对SPA应用的理解 1、单页 Web 应用&#xff08;single page web application&#xff0c;SPA&#xff09;。 2、整个应用只有一个完整的页面 index.html。 3、点击页面中的导航链…

CVE-2023-2928 DedeCMS 文件包含漏洞getshell 漏洞分析

DedeCMS&#xff08;也称为织梦CMS&#xff09;是一款基于PHPMySQL的开源内容管理系统。 在 DedeCMS 5.7.106 及之前的版本中发现一个漏洞。它已被宣布为关键。受此漏洞影响的是未知功能的文件uploads/dede/article_allowurl_edit.php。对参数 allurls 的操作会导致代码注入。…

近期整理的前端面试问题大集合【附带答案版】

目录 1、vue的双向绑定原理是什么&#xff1f;里面的关键点在哪里&#xff1f; 2、实现水平垂直居中的方式&#xff1f; 3、常用伪元素有哪一些&#xff1f; 4、移动端如何适配不同屏幕尺寸&#xff1f; 5、本地存储有哪一些&#xff1f;他们三者有什么区别&#xff1f; …

智慧乡村建设探索:数字乡村引领农村发展新方向

目录 一、智慧乡村建设的内涵与意义 二、数字乡村的发展现状 三、数字乡村引领农村发展的新方向 &#xff08;一&#xff09;推动农业现代化&#xff0c;提升农业生产效率 &#xff08;二&#xff09;培育农村新业态&#xff0c;促进农村产业升级 &#xff08;三&#xf…

陶瓷、高频、普通PCB板材有什么不同?

在电子制造中&#xff0c;印刷电路板&#xff08;PCB&#xff09;板材的选择很重要&#xff0c;将直接决定电路板的性能、成本和适用领域&#xff0c;按照市场上应用最广泛的PCB板材&#xff0c;可分为陶瓷、高频及普通&#xff0c;它们三个有什么不同&#xff1f; 1、材质陶瓷…

COTR 网络(图像匹配)

COTR 网络&#xff08;图像匹配&#xff09; 摘要Abstract1. COTR网络1.1 文献摘要1.2 研究背景1.3 COTR网络架构1.4 创新点1.5 实验1.5.1 数据集1.5.2 具体实施1.5.3 实验数据 1.6 结论 2. COTR模型代码实现总结 摘要 本周学习了图像匹配方向的COTR网络模型&#xff0c;COTR通…

记录一次hss不能防护主机的问题

场景&#xff1a;hss的控制台显示不在防护中&#xff0c;其他云主机并没有这个情况。 故障发生的时间是昨天下午15点半左右&#xff0c;运维同事做了重启网卡的操作。service network restart 排查分析&#xff1a; 于是仔细的查看日志&#xff0c;发现报错如下&#xff1a…

openstack中windows虚拟机时间显示异常问题处理

文章目录 一、问题描述二、元数据信息总结 一、问题描述 openstack创建出windows虚拟机的时候&#xff0c;发现时间和当前时间相差8小时&#xff0c;用起来很难受。 参考&#xff1a;https://www.cnblogs.com/hraa0101/p/11365238.html 二、元数据信息 通过设置镜像的元数据…

边缘计算采集网关如何助力制造企业解决数采问题-天拓四方

一、企业背景 某大型制造企业&#xff0c;位于国内某经济发达的工业园区内&#xff0c;拥有多个生产线和智能化设备&#xff0c;致力于提高生产效率、降低运营成本。随着企业规模的扩大和生产自动化的推进&#xff0c;该企业面临着海量数据处理、实时响应和网络安全等多重挑战…

vmware 中的Ubuntu系统虚拟机忘记root密码强制重置操作

忘记密码情况下&#xff0c;vmware虚拟机重置Ubuntu的root密码 在企业使用的vmware ESXI中重置Ubuntu系统root密码 1-本地电脑安装个人版的vmware workstation&#xff0c;目的&#xff1a;vmware ESXI自带的远程控制台无法输入指定的键盘按键&#xff0c;需要借助外部的远程辅…

spring.rabbitmq.listener.simple.default-requeue-rejected = false 和放入死信队列的区别

目录 一、场景 二、使用 spring.rabbitmq.listener.simple.default-requeue-rejected false 2.1 特点 三、 放入死信队列 四、两种区别 一、场景 当我们使用RabbitMq的时候&#xff0c;我们如果业务中有异常&#xff0c;很有可能造成死循环&#xff0c;因为 在RabbitMQ和…

AI提速 OpenAI 新模型GPT-5今年上线?

这两天&#xff0c;有关OpenAI新模型 GPT-5的消息又多了起来。有知情人士称&#xff0c;OpenAI将在今年年中的某个时候发布GPT-5&#xff0c;很可能是在今年夏天期间。OpenAI CEO 萨姆奥特曼在一次播客采访中透露“GPT-5的智能水平得到提升”。 有趣的是&#xff0c;播客的主理…

Spring Security——08,自定义失败处理

自定义失败处理 一、自定义实现类1.1 实现AccessDeniedHandler1.2 实现AuthenticationEntryPoint 二、配置SpringSecurity三、测试3.1 认证失败3.2 权限不足 一键三连有没有捏~~ 我们还希望在认证失败或者是授权失败的情况下也能和我们的接口一样返回相同结构的json&#xff0c…

AI智慧医疗:探索机器学习在医疗保健中的应用与进展

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟,欢迎关注。提供嵌入式方向的学习指导…

MySQL学习笔记------事务

事务 事务是一组操作的集合&#xff0c;他是一个不可分割的单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这些操作要么同时成功&#xff0c;要么同时失败 事务操作 create table account(id int comment ID,name varchar(10) …

Java 面向对象基础篇【接口、抽象类、实现类之间的关系】

目录 接口&#xff08;Interface&#xff09;&#xff1a;抽象类&#xff08;Abstract Class&#xff09;&#xff1a;实现类&#xff08;Concrete Class&#xff09;&#xff1a; 接口、抽象类、实现类之间的关系类&#xff08;Class&#xff09;&#xff1a; 接口、抽象类、类…

学习嵌入式可以胜任哪一些行业?

嵌入式技术之应用范围甚广&#xff0c;其多见于机器人、无人机、医疗器械以及军工等领域&#xff0c;为学习者带来诸多广泛之职业机遇。嵌入式工程师于此诸领域中扮演关键之角色&#xff0c;负责解决硬件平台适配等诸问题&#xff0c;以为创新提供支撑之力。 虽嵌入式技术与日…

[C++][算法基础]最大异或对(Trie树)

在给定的 N 个整数 &#xff0c;...... 中选出两个进行 xor&#xff08;异或&#xff09;运算&#xff0c;得到的结果最大是多少&#xff1f; 输入格式 第一行输入一个整数 N。 第二行输入 N 个整数 ~ 。 输出格式 输出一个整数表示答案。 数据范围 1≤N≤, 0≤< 输…

lua学习笔记12(多脚本和大G表)

print("*****************************多脚本执行*******************************") print("*****************************全局变量和本地变量*******************************") --全局变量 a114514 b"你干嘛&#xff0c;哎呦" for i1,2 doc&…