力扣日记12.13-【二叉树篇】从中序与后序遍历序列构造二叉树

力扣日记:【二叉树篇】从中序与后序遍历序列构造二叉树

日期:2023.12.13
参考:代码随想录、力扣

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

题目描述

难度:中等

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

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

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

示例 2:

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

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

题解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
# define SOLUTION 2
public:
# if SOLUTION == 1TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {// 递归返回值与参数:返回值为中节点, 参数为中序和后序数组// 从中序与后序遍历序列构造二叉树的步骤// 1. 如果后序数组为空, 则为空节点(终止条件)if (postorder.size() == 0) return nullptr;  // 为空节点// 2. 根据后序数组最后一个值得到中节点值int nodeVal = postorder[postorder.size() - 1];  // 后序数组最后一个值为中节点值TreeNode* node = new TreeNode(nodeVal); // 构造中节点// 注意如果是叶子节点, 则不需要再去切割, 直接返回当前节点if (postorder.size() == 1) return node;// 3. 寻找中序数组位置作切割点int index = 0;for (int i = 0; i < inorder.size(); i++) {if (inorder[i] == nodeVal) {index = i;  // index 为中节点值对应序号, 则[0, index)为左子树, [index + 1, size)为右子树, 注意统一区间开闭 }}// 4. 根据此切割点对中序数组进行切割vector<int> inorderLeft(inorder.begin(), inorder.begin() + index);  // [0, index)vector<int> inorderRight(inorder.begin() + index + 1, inorder.end());   // [index + 1, size)// 5. 再根据切割后中序数组左右区间长度对后序数组进行切割vector<int> postorderLeft(postorder.begin(), postorder.begin() + inorderLeft.size()); // [0, left.size)vector<int> postorderRight(postorder.begin() + inorderLeft.size(), postorder.begin() + inorderLeft.size() + inorderRight.size()); // [left.size, left.size + right.size)// 6. 将中序数组与后序数组的左子树区间进行递归处理, 递归返回值为左子树的根节点,作为当前node左节点node->left = buildTree(inorderLeft, postorderLeft);   // 中序和后序的左子树遍历数组都分别按中序和后序遍历// 7. 将中序数组与后序数组的右子树区间进行递归处理node->right = buildTree(inorderRight, postorderRight);return node;    // 返回已经接上左右节点的中节点}
# elif SOLUTION == 2    // 优化:用下标索引,不需要每次构建子数组TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int inorderBegin = 0, inorderEnd = inorder.size();  // [0, size)int postorderBegin = 0, postorderEnd = postorder.size();    // [0, size)return traversal(inorder, inorderBegin, inorderEnd, postorder, postorderBegin, postorderEnd);}TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {// 递归返回值与参数:返回值为中节点, 参数为原始中序后序数组, 以及用来表示当前中后序数组的下标// 不变量:左闭右开// 从中序与后序遍历序列构造二叉树的步骤// 1. 如果当前后序数组为空, 则为空节点(终止条件)if (postorderEnd - postorderBegin == 0) return nullptr;  // 为空节点 [Begin, Begin)// 2. 根据后序数组最后一个值得到中节点值int nodeVal = postorder[postorderEnd - 1];  // 后序数组最后一个值为中节点值, 右开, 则需-1TreeNode* node = new TreeNode(nodeVal); // 构造中节点// 注意如果是叶子节点, 则不需要再去切割, 直接返回当前节点if (postorderEnd - postorderBegin == 1) return node;// 3. 寻找中序数组位置作切割点int index = 0;for (int i = inorderBegin; i < inorderEnd; i++) {if (inorder[i] == nodeVal) {index = i;  // index 为中节点值对应序号, 则[inorderBegin, index)为左子树, [index + 1, inorderEnd)为右子树, 注意统一区间开闭 }}// 4. 根据此切割点对中序数组进行切割int inorderLeftBegin = inorderBegin; // 左子树区间的开始下标(左闭)int inorderLeftEnd = index; // 左子树区间的结束下标(右开)int inorderRightBegin = index + 1;  // 右子树区间int inorderRightEnd = inorderEnd;// 5. 再根据切割后中序数组左右区间长度对后序数组进行切割int LeftSize = inorderLeftEnd - inorderLeftBegin;    // 左子树大小int postorderLeftBegin = postorderBegin;int postorderLeftEnd = postorderBegin + LeftSize;    // 后序与中序的左子树数组大小一致, LeftSize: [postorderLeftBegin, postorderLeftBegin + LeftSize)int RightSize = inorderRightEnd - inorderRightBegin;int postorderRightBegin = postorderLeftEnd; // 左闭int postorderRightEnd = postorderLeftEnd + RightSize;// 6. 将中序数组与后序数组的左子树区间进行递归处理, 递归返回值为左子树的根节点,作为当前node左节点node->left = traversal(inorder, inorderLeftBegin, inorderLeftEnd, postorder, postorderLeftBegin, postorderLeftEnd);   // 中序和后序的左子树遍历数组都分别按中序和后序遍历// 7. 将中序数组与后序数组的右子树区间进行递归处理node->right = traversal(inorder, inorderRightBegin, inorderRightEnd, postorder, postorderRightBegin, postorderRightEnd);return node;    // 返回已经接上左右节点的中节点}
# endif
};

复杂度

时间复杂度:
空间复杂度:

思路总结

  • 从中序与后序遍历序列构造二叉树的步骤
      1. 如果后序数组为空, 则为空节点
      2. 根据后序数组最后一个值得到中节点值
      3. 寻找中序数组位置作切割点
      4. 根据此切割点对中序数组进行切割
      5. 再根据切割后中序数组左右区间长度对后序数组进行切割
      6. 将中序数组与后序数组的左子树区间进行递归处理(两个左子树区间数组分别为左子树的中序数组和后序数组)
      7. 将中序数组与后序数组的右子树区间进行递归处理
  • 示意图
    在这里插入图片描述
  • 对于第二种解法,即用下标索引表示子数组(而不是直接构造子数组),要分别确定好左右子树的中序和后序数组的开始、结束下标。统一用左闭右开来表示。相对繁琐一些,但时间和空间复杂度更优化。

相关题目:105. 从前序与中序遍历序列构造二叉树

题目描述

难度:中等

给定两个整数数组 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]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

题解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// 1. 如果前序数组为空, 则为空节点if (preorder.size() == 0)   return nullptr;// 2. 根据前序数组第一个值得到中节点值int nodeVal = preorder[0];// 构造中节点TreeNode* node = new TreeNode(nodeVal);// 如果是叶子节点直接返回if (preorder.size() == 1)   return node;// 3. 寻找中序数组位置作切割点int index = 0;for (int i = 0; i < inorder.size(); i++) {if (inorder[i] == nodeVal) {index = i;}}// 4. 根据此切割点对中序数组进行切割vector<int> inorderLeft(inorder.begin(), inorder.begin() + index);vector<int> inorderRight(inorder.begin() + index + 1, inorder.end());// 5. 再根据切割后的中序数组左右区间长度对前序数组进行切割vector<int> preorderLeft(preorder.begin() + 1, preorder.begin() + 1 + inorderLeft.size());  // 第二个值开始vector<int> preorderRight(preorder.begin() + 1 + inorderLeft.size(), preorder.end());// 6. 将中序数组与前序数组的左子树区间进行递归处理(两个左子树区间数组分别为左子树的中序数组和前序数组)node->left = buildTree(preorderLeft, inorderLeft);// 7. 将中序数组与前序数组的右子树区间进行递归处理node->right = buildTree(preorderRight, inorderRight);return node;}
};

复杂度

思路总结

  • 与 从后序与中序遍历序列构造二叉树 的思路基本一致
  • 从前序与中序遍历序列构造二叉树的步骤(前序:中左右;中序:左中右)
      1. 如果前序数组为空, 则为空节点
      2. 根据前序数组第一个值得到中节点值
      3. 寻找中序数组位置作切割点
      4. 根据此切割点对中序数组进行切割
      5. 再根据切割后的中序数组左右区间长度对前序数组进行切割
      6. 将中序数组与前序数组的左子树区间进行递归处理(两个左子树区间数组分别为左子树的中序数组和前序数组)
      7. 将中序数组与前序数组的右子树区间进行递归处理
  • 这里要明确一点:前序和中序、后序和中序都可以分别唯一确定一棵二叉树;但前序和后序不能唯一确定一棵二叉树!因为没有中序遍历无法确定左右部分,也就是无法分割。
    • 在这里插入图片描述
    • 上面两棵树的前序、后序都分别相等

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

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

相关文章

OpenCV极坐标变换函数warpPolar的使用

学更好的别人&#xff0c; 做更好的自己。 ——《微卡智享》 本文长度为1702字&#xff0c;预计阅读4分钟 前言 前阵子在做方案时&#xff0c;得了几张骨钉的图片&#xff0c;骨科耗材批号效期管理一直是比较麻烦的&#xff0c;贴RFID标签成本太高&#xff0c;所以一般考虑还是…

深入解析Spring Boot集成MyBatis的多种方式

文章目录 1. 引言2. 传统的XML配置方式2.1 引入依赖2.2 配置数据源和MyBatis2.3 编写Mapper接口和XML映射文件2.4 使用Mapper 3. 注解配置方式3.1 引入依赖3.2 配置数据源和MyBatis3.3 编写Mapper接口3.4 使用Mapper 4. MyBatis动态SQL4.1 使用XML配置方式4.2 使用注解配置方式…

Qt/C++视频监控安卓版/多通道显示视频画面/录像存储/视频播放安卓版/ffmpeg安卓

一、前言 随着监控行业的发展&#xff0c;越来越多的用户场景是需要在手机上查看监控&#xff0c;而之前主要的监控系统都是在PC端&#xff0c;毕竟PC端屏幕大&#xff0c;能够看到的画面多&#xff0c;解码性能也强劲。早期的手机估计性能弱鸡&#xff0c;而现在的手机性能不…

Facebook广告系统结构

Facebook广告系统是一个复杂的大型系统&#xff0c;由多个组件和子系统相互配合工作&#xff0c;实现了广告的投放、拍卖、个性化推荐和效果评估等功能。下面小编讲讲Facebook广告系统的结构。 1、广告管理界面 广告管理界面是广告主与Facebook进行交互的入口&#xff0c;广告…

如何在Docker部署draw.io流程图软件并实现公网远程访问

前言 提到流程图&#xff0c;大家第一时间可能会想到Visio&#xff0c;不可否认&#xff0c;VIsio确实是功能强大&#xff0c;但是软件为收费&#xff0c;并且因为其功能强大&#xff0c;导致安装需要很多的系统内存&#xff0c;并且是不可跨平台使用。所以&#xff0c;今天给…

c语言链表的基本操作

在C语言中&#xff0c;链表是一种常见的数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含一个数据元素和一个指向下一个节点的指针。链表的基本操作包括创建、插入、删除和遍历等。 下面是一个简单的链表节点结构体定义&#xff1a; struct Node { int da…

Leaflet.Graticule源码分析以及经纬度汉化展示

目录 前言 一、源码分析 1、类图设计 2、时序调用 3、调用说明 二、经纬度汉化 1、改造前 2、汉化 3、改造效果 总结 前言 在之前的博客基于Leaflet的Webgis经纬网格生成实践中&#xff0c;已经深入介绍了Leaflet.Graticule的实际使用方法和进行了简单的源码分析。认…

C语言之函数式宏

目录 函数和数据类型 函数式宏 函数和函数式宏 函数式宏和对象式宏 不带参数的函数式宏 函数式宏和逗号运算符 函数式宏和函数类似并且比函数更加灵活&#xff0c;下面我们就来学习函数式宏的相关内容。 函数和数据类型 我们来编写一个程序&#xff0c;它能计算出所读取…

『PyTorch』张量和函数之gather()函数

文章目录 PyTorch中的选择函数gather()函数 参考文献 PyTorch中的选择函数 gather()函数 import torch a torch.arange(1, 16).reshape(5, 3) """ result: a [[1, 2, 3],[4, 5, 6],[7, 8, 9],[10, 11, 12],[13, 14, 15]] """# 定义两个index…

注册与回调

C 再谈谈注册(本质是建立映射)与回调 在之前的博文中&#xff0c; 我们探讨过映射的重要作用&#xff0c; 请直接看&#xff1a;http://blog.csdn.net/stpeace/article/details/39452203, 在那篇文章中&#xff0c; 我们是用STL中的map来做的&#xff0c; map建立的是key-value…

ChatGLM-6B模型结构组件源码阅读

一、前言 本文将介绍ChatGLM-6B的模型结构组件源码。 代练链接&#xff1a;https://huggingface.co/THUDM/chatglm-6b/blob/main/modeling_chatglm.py 二、激活函数 torch.jit.script def gelu_impl(x):"""OpenAIs gelu implementation."""r…

云演 Can you getshell?

1、扫目录&#xff0c;看看到upload.php,找到上传点 2、只让上传jpg gif png&#xff0c;上传图片写码 <?php eval($_POST[c]);?>这个码不行 换马 <script language"php">eval($_REQUEST[c])</script>3、蚁剑连接、得到flag

【MyBatis-Plus】MyBatis进阶使用

目录 一、MyBatis-Plus简介 1.1 介绍 1.2 优点 1.3 结构 二、MyBatis-Plus基本使用 2.1 配置 2.2 代码生成 2.3 CRUD接口测试 三、MyBatis-Plus策略详解 3.1 主键生成策略 3.2 雪花ID生成器 3.3 字段自动填充策略 3.4 逻辑删除 四、MyBatis-Plus插件使用 4.1 乐…

TrustZone之完成器:外围设备和内存

到目前为止,在本指南中,我们集中讨论了处理器,但TrustZone远不止是一组处理器功能。要充分利用TrustZone功能,我们还需要系统其余部分的支持。以下是一个启用了TrustZone的系统示例: 本节探讨了该系统中的关键组件以及它们在TrustZone中的作用。 完成器:外围设备…

服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌X系列服务器&#xff0c;4块SAS硬盘组建了一组RAID5阵列&#xff0c;还有1块磁盘作为热备盘使用。服务器上层安装的linux操作系统&#xff0c;操作系统上部署了一个基于oracle数据库的OA&#xff08;oracle已经不再为该OA系统提供后续服务…

【c语言】【visual studio】动态内存管理,malloc,calloc,realloc详解。

引言&#xff1a;随着大一期末的到来&#xff0c;想必许多学生都学到内存的动态管理这一部分了&#xff0c;看望这篇博客后&#xff0c;希望能解除你心中对这一章节的疑惑。 (・∀・(・∀・(・∀・*) 1.malloc详解 malloc的头文件是#include <sdtlib.h>,malloc - C Ref…

Spring Cloud + Vue前后端分离-第5章 单表管理功能前后端开发

Spring Cloud Vue前后端分离-第5章 单表管理功能前后端开发 完成单表的增删改查 控台单表增删改查的前后端开发&#xff0c;重点学习前后端数据交互&#xff0c;vue ajax库axios的使用等 通用组件开发:分页、确认框、提示框、等待框等 常用的公共组件:确认框、提示框、等待…

【Linux】多线程编程

目录 1. 线程基础知识 2. 线程创建 3. 线程ID&#xff08;TID&#xff09; 4. 线程终止 5. 线程取消 6. 线程等待 7. 线程分离 8. 线程互斥 8.1 初始化互斥量 8.2 销毁互斥量 8.3 互斥量加锁和解锁 9. 可重入和线程安全 10. 线程同步之条件变量 10.1 初始化条件变…

一文了解Tomcat

文章目录 1、Tomcat介绍2、Tomcat使用配置2.1、Tomcat下载启动2.2、Tomcat启动乱码2.3、Tomcat端口号修改 3、Tomcat项目部署4、IDEA中使用Tomcat方式 1、Tomcat介绍 什么是Tomcat ​ Tomcat是Apache软件基金会一个核心项目&#xff0c;是一个开源免费的轻量级web服务器&#x…

【算法Hot100系列】最长回文子串

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…