【算法】递归+深搜+哈希表:889.根据前序和后序遍历构造二叉树

目录

1、题目链接

相似题目:

2、题目

​3、解法(针对无重复值,哈希表+递归)

函数头-----找出重复子问题

函数体---解决子问题

4、代码


1、题目链接

889.根据前序和后序遍历构造二叉树(LeetCode)

相似题目:

105.从前序与中序遍历序列构造二叉树(LeetCode)

106.从中序与后序遍历序列构造二叉树(LeetCode)


2、题目


3、解法(针对无重复值,哈希表+递归)

前序:根节点、左子树、右子树
后序:左子树、右子树、根节点

二叉树的根节点一定是前序遍历的第一个节点,也是后序遍历的最后一个节点。

接下来,我们需要确定二叉树的左子树范围和右子树范围。

        首先,仅凭前序和后序,得不到唯一的二叉树。结果可能有多个。
        没有中序遍历的情况下,无法区分哪些节点属于左子树,哪些属于右子树。
        第二个元素我们默认他是左子树的根节点。

函数头-----找出重复子问题

深搜函数头:preorder前序数组,

                        root :根节点在前序的下标

                        left:根节点所在子树的左边界

                        right:根节点所在子树的右边界

TreeNode* dfs(const vector<int>& preorder, int root, int left, int right)

函数体---解决子问题

哈希表 hash,它存储了后序遍历中每个节点的位置。在函数的开头,我们可以找到任意节点在后序遍历中的位置。

  1. 如果 left >right ,说明范围为空,直接返回空节点。
  2. 否则,我们构造一个新的节点 node ,它的值为前序遍历中的第一个节点的值,也就是 preorder[root]。
  3. 如果 left 等于 right ,说明 root 没有左子树也没有右子树,直接返回 root。
  4. 否则,左子树的根节点的值为 preorder[ root + 1],我们在后序遍历中找到 preorder[ root + 1] 的位置,记为 pos_root。
    1. 那么左子树的节点个数 left_size = pos_root − left + 1,由此可知左子树后序遍历中的范围是 [left , pos_root ],右子树在后序遍历中的范围是 [pos_root + 1, right −1]。
  5. 知道了左右子树的范围,我们就可以递归地重建左右子树,然后将左右子树的根节点分别作为 node 的左右子节点。最后返回 node。

        if (left > right)return NULL;TreeNode* node = new TreeNode(preorder[root]);//构建根节点//非常重要!!!影响整个代码的通过//root 没有左子树也没有右子树,直接返回 root。if (left == right)return node;int pos_root = hash[preorder[root + 1]];    //左子树的root在后序的下标int left_size = pos_root - left + 1; //左子树结点数(含root)int right_root = root + left_size + 1;//右子树根节点在前序中的下标node->left = dfs(preorder, root+1, left, pos_root);node->right = dfs(preorder, right_root, pos_root + 1, right - 1);


4、代码

class Solution {//仅仅依靠前序、后序,会有存在多个二叉树
public:unordered_map<int, int> hash;//root 在pre的下标TreeNode* dfs(const vector<int>& preorder, int root, int left, int right){if (left > right)return NULL;TreeNode* node = new TreeNode(preorder[root]);//构建根节点//非常重要!!!影响整个代码的通过//root 没有左子树也没有右子树,直接返回 root。if (left == right)return node;int pos_root = hash[preorder[root + 1]];    //左子树的root在后序的下标int left_size = pos_root - left + 1; //左子树结点数(含root)int right_root = root + left_size + 1;//右子树根节点在前序中的下标node->left = dfs(preorder, root+1, left, pos_root);node->right = dfs(preorder, right_root, pos_root + 1, right - 1);return node;}TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {//postorder填充hashfor (int i = 0; i < postorder.size(); i++){hash[postorder[i]] = i;}return dfs(preorder, 0, 0, postorder.size() - 1);}
};

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

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

相关文章

微服务的注册中心Nacos

前言 Nacos是阿里巴巴开源的服务注册中心以及配置中心&#xff0c;致力于给开发者提供一款便捷、简单上手的开源框架。 Nacos究竟有什么惊人的地方呢&#xff1f;看下图&#xff1a; 从上图不难看出阿里巴巴的野心&#xff0c;一个Nacos干掉了Spring Cloud的三大组件&#xf…

蓝桥杯-网络安全比赛题目-遗漏的压缩包

小蓝同学给你发来了他自己开发的网站链接&#xff0c; 他说他故意留下了一个压缩包文件&#xff0c;里面有网站的源代码&#xff0c; 他想考验一下你的网络安全技能。 &#xff08;点击“下发赛题”后&#xff0c;你将得到一个http链接。如果该链接自动跳转到https&#xff0c;…

ubuntu中安装mysql

一、注意版本问题 ubuntu常用的版本是16.4&#xff0c;18.4,对应的mysql文件也不同&#xff0c;注意不要下载错误。 二、注意更换apt的源 sudo cat /etc/apt/sources.list查看现在的数据源&#xff0c;我更换了阿里的数据源。更换语句如下&#xff1a; sed -i s/http:\/\/…

java的体系结构

1. 题记&#xff1a; 其实很早就打算来写java的体系结构这一文章&#xff0c;但是有诸多担忧就一直搁置。其一担心自己水平有限&#xff0c;恐不能讲得太透彻&#xff0c;因为java的体系结构宏大精深。其二不知道怎么去把控文章的难度及深度&#xff0c;因为需要给大部分看&am…

PostgreSQL技术内幕17:PG分区表

文章目录 0.简介1.概念介绍2.分区表技术产生的背景3.分区类型及使用方式4.实现原理4.1 分区表创建4.2 分区表查询4.3 分区表写入4.4 分区表删除 0.简介 本文主要介绍PG中分区表的概念&#xff0c;产生分区表技术的原因&#xff0c;使用方式和其内部实现原理&#xff0c;旨在能…

Ubuntu - 进入紧急模式,无法进入桌面

目录 一、问题 二、分析原因 三、解决 四、参考 一、问题 重新安装VMVare之后&#xff0c;将之前的虚拟机加载不进来 二、分析原因 查看系统错误日志 journalctl -xb | grep Failed mnt挂载找不到了 三、解决 查看系统错误日志 如果是磁盘错误&#xff0c;此时终端会有…

【Spring】——SpringBoot项目创建

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 引入 一&#xff1a;介绍 二&#xff1a;Spring Boot项目创建 0&#xff1a;项目目录 1&#xff1a…

从0开始搭建一个生产级SpringBoot2.0.X项目(十二)SpringBoot接口SpringSecurity JWT鉴权

前言 最近有个想法想整理一个内容比较完整springboot项目初始化Demo。 SpringBoot接口权限控制 SpringSecurity 接口使用 Bearer token类型 JWT 鉴权 一、pom文件新增依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>s…

Maven 下载配置 详解 我的学习笔记

Maven 下载配置 详解 我的学习笔记 一、Maven 简介二、maven安装配置三、maven基本使用四、idea配置mavenidea配置maven环境maven坐标idea创建maven项目配置Maven-Helper插件 五、依赖管理 一、Maven 简介 Apache Maven 是一个项目管理和构建工具&#xff0c;它基于项目对象模型…

Windows Server2012 R2搭建NFS服务器

正文共&#xff1a;1024 字 23 图&#xff0c;预估阅读时间&#xff1a;1 分钟 在测试vCenter的集群操作时&#xff0c;出现了共享vSAN错误的问题&#xff0c;导致无法继续。我也只好先创建一个共享NFS&#xff08;Network File System&#xff0c;网络文件系统&#xff09;存储…

HarmonyOs DevEco Studio小技巧28--部分鸿蒙生命周期详解

目录 前言 页面和自定义组件生命周期 页面生命周期 onPageShow --- 表示页面已经显示 onPageHide --- 表示页面已经隐藏 onBackPress --- 表示用户点击了返回键 组件生命周期 aboutToAppear --- 表示组件即将出现 onDidBuild --- 表示组件已经构建完成 aboutToDisap…

dolphin 配置data 从文件导入hive

datax 支持多种数据源的相互读写&#xff0c;作为开源软件&#xff0c;提供了离线采集功能&#xff0c;方便系统开发&#xff0c;过程中遇到诸多配置&#xff0c;需要开发者自己探索&#xff0c;免费同样有成本 配置模板 {"setting": {},"job": {"s…

高效管理iPhone存储:苹果手机怎么删除相似照片

在使用iPhone的过程中&#xff0c;我们经常会遇到存储空间不足的问题&#xff0c;尤其是当相册中充满了大量相似照片时。这些照片不仅占用了宝贵的存储空间&#xff0c;还可能使iPhone出现运行卡顿的情况。因此&#xff0c;我们迫切需要寻找苹果手机怎么删除相似照片的方法&…

C++:set详解

文章目录 前言一、set概念介绍二、set的使用1. 插入删除相关2. 查找相关1&#xff09;find2&#xff09;count3&#xff09;lower_bound与upper_bound4&#xff09;equal_range 三、set的值是不能修改的原理四、基于哈希表的set总结 前言 根据应用场景的不同&#xff0c;STL总…

leetcode:杨辉三角

题目链接 class Solution { public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv(numRows);//生成一个长度为5&#xff0c;元素为vector<int>的顺序表for (int i 0; i < numRows; i)//对生成的顺序表初始化&#xff…

【力扣打卡系列】单调栈

坚持按题型打卡&刷&梳理力扣算法题系列&#xff0c;语言为go&#xff0c;Day20 单调栈 题目描述 解题思路 单调栈 后进先出 记录的数据加在最上面丢掉数据也先从最上面开始 单调性 记录t[i]之前会先把所有小于等于t[i]的数据丢掉&#xff0c;不可能出现上面大下面小的…

二次封装 el-pagination 组件存在的问题

在使用 Element Plus 组件时&#xff0c;有时会遇到组件不完全符合需求的情况&#xff0c;这时可能需要对其进行二次封装。在封装 Pagination 组件时&#xff0c;我们会发现一些属性和函数无法正常使用&#xff0c;下面将详细探讨这些问题&#xff0c;并提供一下思路和想法。 …

通俗易懂讲STM32为GPIO的8种模式(上拉输入、下拉输入、模拟输入、浮空输入,开漏输出,推挽输出)

本文参照这篇博客---易于理解深刻理解GPIO(上拉输入、下拉输入、模拟输入、浮空输入&#xff0c;开漏输出&#xff0c;推挽输出的区别&#xff0c;以STM32为例)_下拉输出-CSDN博客 一、输入模式 上拉输入 一句话总结&#xff1a;接上拉电阻对输入的低电平能够有效的读取&…

单元测试日志打印相关接口及类 Logger

LoggerFactory 简介 单元测试常用日志打印工具LoggerFactory。 LoggerFactory 代码结构 LoggerFactory 是 JUnit 平台中的一个类&#xff0c;用于创建 Logger 实例。它被设计用于提供日志记录功能&#xff0c;使得 JUnit 在执行测试时能够记录信息、警告、错误等。 LoggerFact…

【万字总结】数据结构常考应用大题做法画法详解_树_哈希表_图_排序大总结

文章目录 1.树相关应用大题1.1 已知二叉树的中序序列和前序or中序&#xff0c;画出二叉树1.2 二叉树的遍历、树的遍历、森林的遍历总结1.3二叉树与森林之间的转换1.3.1 已知树的先序序列和中序序列&#xff0c;画出森林 1.4 二叉树的线索化1.5 二叉排序树1.5.1 二叉排序树的删除…