代码随想录笔记|C++数据结构与算法学习笔记-二叉树(六)|LeetCode106.从中序与后序遍历序列构造二叉树、654.最大二叉树

news/2024/6/20 21:05:38/文章来源:https://blog.csdn.net/caiziming_001/article/details/137277851

文章目录

  • 106.从中序与后序遍历序列构造二叉树
    • 构造二叉树的流程
    • 伪代码
    • 注意细节
    • CPP代码
  • 654.最大二叉树
    • 构造二叉树的流程
    • 伪代码
    • CPP代码

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

力扣题目链接

文章讲解:106.从中序与后序遍历序列构造二叉树

视频讲解:坑很多!来看看你掉过几次坑 | LeetCode:106.从中序与后序遍历序列构造二叉树

构造二叉树的流程

举一个例子:

中序:9 3 15 20 7

后序:9 15 7 20 3

我们可以从后序中确定根结点是3;那么再切换到中序可知,左区间是9,右区间是15,20,7;再切换回后序9,15,7,20中,9是左子树里面的,15,7,20是右子树的元素;然后再从后序确定中间结点是20;再回到中序,可以确定20的左结点为15,右结点为7.

这样构造出整个二叉树。

总结上述流程,就是首先从后序确定中间结点,然后从中序确定左右子树,再到后序确定子树的中间结点。

在代码中整个过程分为6步:

  1. 后序数组为0,返回空结点

  2. 后序数组最后一个元素为结点元素

  3. 寻找中序数组位置作中序左右区间的切割点

  4. 切割中序数组:形成左中序数组 右中序数组

  5. 切割后序数组,拿切中序数组形成的左中序数组去切,因为他俩都是一样的:形成左后序 右后序

  6. 递归处理左区间后区间

伪代码

  • 确定递归函数的参数返回值:返回值是根据中序和后序构造完后的二叉树的根结点。
TreeNode* traversal(inorder, postorder){}
  • 确定递归函数的终止条件:后序数组为0
  1. 后序数组为0,返回空结点
if (posrorder.size == 0) return nullptr;
  • 确定单层递归逻辑:
  1. 后序数组的最后一个元素为结点元素
rootvalue = postorder[postorder.size - 1];
root = new TreeNode(rootvalue);
if(postorder.size == 1) return root;//如果只有一个结点的情况
  1. 寻找中序数组位置作切割点
index = 0;
for (index = 0; index < inorder.size; index++){if (inorder[index] == rootvalue)break;	//这里为啥要break 因为这里我们是根据index来切割,找到index了目的就达到了
}
  1. 切割中序数组、5. 切后序数组

切中序数组 左中序 右中序

切后序数组 左后序 右后序

// 切割中序数组
// 左闭右开区间:[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);// 切割后序数组
// 依然左闭右开,注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
  1. 递归处理左区间后区间
root->left = traversal(左中序,左后序);
root->right = traversal(右中序,右后序);
return root;

注意细节

  • 在切割区间的时候,一定要注意循环不变量,坚持左闭右开或者左开右必
  • 一定要先切中序数组,再切后序数组。这样才能区分出来相互关系。

CPP代码

class Solution {
private:TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {if (postorder.size() == 0) return NULL;// 后序遍历数组最后一个元素,就是当前的中间节点int rootValue = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootValue);// 叶子节点if (postorder.size() == 1) return root;// 找到中序遍历的切割点int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 左闭右开区间:[0, delimiterIndex)vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开,注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());// [leftInorder.size(), end)vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

654.最大二叉树

力扣题目地址

文章讲解:654.最大二叉树

视频讲解:又是构造二叉树,又有很多坑!| LeetCode:654.最大二叉树

构造二叉树的流程

选择数组中最大的书,来切割数组,左区间作为左子树,右区间作为右子树,如此循环构造一颗最大二叉树。

比如说数组:3 2 1 6 0 5

6是最大的数,3 2 1是左子树,3又是最大的数作为6的左孩子;2 1是3的右区间作为右子树,2又是最大的作为3的右孩子,1是2的右区间,所以1是2的右孩子,由此得出二叉树

​ 6

/ \

3 5

\ /

​ 2 0

​ \

​ 1

凡是构造二叉树类的题目一律使用前序遍历,前序遍历是中左右,一定要先构造中,只有构造出根结点才好去构造左子树和右子树

伪代码

  • 确定参数和返回值:参数传入的是存放元素的数组,返回该数组构造的二叉树的头结点,返回类型是指向节点的指针
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
  • 确定终止条件:当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。
TreeNode* node = new TreeNode(0); //定义新结点
if (nums.size() == 1){		node->val = nums[0];return node;
}
  • 确定单层递归的逻辑
  1. 先找到数组中最大的值对应的下标,最大的值构造根结点,下标来分割数组
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++){if (nums[i] > maxValue){maxValue = nums[i];maxValueIndex = i;}
}
TreeNode* node = new TreeNode(0);
node->val = maxValue;
  1. 最大值所在的下标左区间 构造左子树:判断maxValueIndex > 0要保证左区间至少有一个数值
if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);
}
  1. 最大值所在的下标右区间 构造右子树:判断maxValueIndex < (nums.size() - 1)确保右区间至少有一个数值。
if (maxValueIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());node->right = constructMaximumBinaryTree(newVec);
}

CPP代码

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* node = new TreeNode(0);if (nums.size() == 1) {node->val = nums[0];return node;}// 找到数组中最大的值和对应的下标int maxValue = 0;int maxValueIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxValueIndex = i;}}node->val = maxValue;// 最大值所在的下标左区间 构造左子树if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);}// 最大值所在的下标右区间 构造右子树if (maxValueIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());node->right = constructMaximumBinaryTree(newVec);}return node;}
};

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

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

相关文章

Windows 电脑麦克风 自动启用/禁用 小玩具!

WinMicrophone Windows 系统的 麦克风设备&#xff08;启用/禁用&#xff09;切换驱动&#xff01;它是小巧且快速的&#xff0c;它能够自动的检测并切换麦克风的情况。 您可以在软件包仓库中找到发布版本的exe包&#xff0c;无需安装&#xff01;其能够大大增大您在Windows中…

6.3物联网RK3399项目开发实录-驱动开发之I2C 使用(wulianjishu666)

物联网开发源码案例集&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1kfPDpYZpm_G0GBLAup3KTQ?pwdvgvv I2C 使用 简介 AIO-3399J 开发板上有 9 个片上 I2C 控制器&#xff0c;各个 I2C 的使用情况如下表&#xff1a; 本文主要描述如何在该开发板上配置 I2C。 配置…

WebCopilot:一款功能强大的子域名枚举和安全漏洞扫描工具

关于WebCopilot WebCopilot是一款功能强大的子域名枚举和安全漏洞扫描工具&#xff0c;该工具能够枚举目标域名下的子域名&#xff0c;并使用不同的开源工具检测目标存在的安全漏洞。 工具运行机制 WebCopilot首先会使用assetsfinder、submaster、subfinder、accumt、finddom…

大数据学习第十二天(hadoop概念)

1、服务器之间数据文件传递 1&#xff09;服务器之间传递数据&#xff0c;依赖ssh协议 2&#xff09;http协议是web网站之间的通讯协议&#xff0c;用户可已通过http网址访问到对应网站数据 3&#xff09;ssh协议是服务器之间&#xff0c;或windos和服务器之间传递的数据的协议…

C语言第三十九弹---预处理(上)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 预处理 1、预定义符号 2、#define定义常量 3、#define定义宏 4、带有副作用的宏参数 5、宏替换的规则 6、宏和函数的对比 总结 在C语言中&#xff0c;预处…

阿里云2核4G云服务器支持多少人同时在线?并发数计算?

阿里云2核4G服务器多少钱一年&#xff1f;2核4G配置1个月多少钱&#xff1f;2核4G服务器30元3个月、轻量应用服务器2核4G4M带宽165元一年、企业用户2核4G5M带宽199元一年。可以在阿里云CLUB中心查看 aliyun.club 当前最新2核4G服务器精准报价、优惠券和活动信息。 阿里云官方2…

蓝奏云直链获取在线解析网站源码

源码简介 蓝奏云直链获取在线解析网站源码 蓝奏云链接解析 本地API接口 支持有无密码和短期直链和永久直链&#xff0c;同时还可以显示文件名和大小。 这个解析器无需数据库即可搭建&#xff0c;API接口已经本地化&#xff0c;非常简单易用。 安装环境 php5.6 搭建教程 …

在编程中使用中文到底该不该??

看到知乎上有个热门问题&#xff0c;为什么很多人反对中文在编程中的使用&#xff1f; 这个问题有几百万的浏览热度&#xff0c;其中排名第一的回答非常简洁&#xff0c;我深以为然&#xff1a; 在国内做开发&#xff0c;用中文写注释、写文档&#xff0c;是非常好的习惯&…

前端工程师————HTML5学习

HTML5基础 开发工具很多&#xff0c;其中Hbulider较好用&#xff0c;下载网址如下&#xff1a; DCloud - HBuilder、HBuilderX、uni-app、uniapp、5、5plus、mui、wap2app、流应用、HTML5、小程序开发、跨平台App、多端框架 html表示整个页面 head表示搜素框 body表示内容 ti…

Java练习

这个练习我用到了继承&#xff0c;多态和封装。 1.继承&#xff1a; Animal 类是一个抽象类&#xff0c;它有两个子类 Dog 和 Cat。 Dog 和 Cat 分别继承自 Animal 类&#xff0c;因此它们可以使用 Animal 类中定义的属性和方法&#xff0c;同时也可以有自己特有的属性和方法。…

【Java代码审计】SSTI模板注入篇

【Java代码审计】SSTI模板注入篇 1.概述2.Velocity 模板引擎3.Thymeleaf 模板注入复现普通url作为视图 4.SSTI 漏洞修复白名单控制跳转模版设置response参数 1.概述 模板引擎支持使用静态模板文件&#xff0c;在运行时用 HTML 页面中的实际值替换变量/占位符&#xff0c;从而让…

C++要学到什么程度才能找到实习?

在考虑 C 学习到何种程度可以找到实习时&#xff0c;以下是一些具体的方向和建议。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&#xff0c;我…

java学习之路-数组定义与使用

目录 ​编辑 1.什么是数组 2.数组的创建及其初始化 2.1数组的创建 2.2数组的初始化 3.数组的使用 3.1数组元素访问 3.2遍历数组 4.数组是引用类型 4.1jvm的内存分布 4.2基本类型变量与引用类型变量的区别 4.3引用变量详解 4.4 null 5.数组的使用场景 5.1存储数据 5…

使用Vue实现CSS过渡和动画

01-初识动画和过渡 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>使用vue实现css过渡和动画&l…

数据结构——遍历二叉树和线索二叉树,树和森林

目录 1.遍历的算法实现 1.先序遍历 代码示例&#xff1a; 2.中序遍历 代码示例&#xff1a; 3.后序遍历 代码示例&#xff1a; 4.遍历算法的分析 2.遍历二叉树的非递归算法 1.中序遍历非递归算法 代码示例&#xff1a; 3.二叉树的层次遍历 代码示例&#xff1a; 4.二…

c#仿ppt案例

画曲线 namespace ppt2024 {public partial class Form1 : Form{public Form1(){InitializeComponent();}//存放所有点的位置信息List<Point> lstPosition new List<Point>();//控制开始画的时机bool isDrawing false;//鼠标点击开始画private void Form1_MouseD…

网络原理 - HTTP / HTTPS(2)——http请求

目录 一、认识 “方法”&#xff08;method&#xff09; 1、GET方法 2、POST方法 &#xff08;1&#xff09;登录 &#xff08;2&#xff09;上传 &#xff08;3&#xff09;GET和POST使用习惯 3、GET方法和POST方法的区别 正确滴 关于一些网上的说法&#xff0c;错误滴…

电商技术揭秘四:电商平台的物流管理系统

文章目录 引言一、物流管理系统的功能与架构1.1 物流管理系统在电商平台中的作用概述保障订单的及时配送优化库存管理控制运营成本提升客户服务水平支持数据驱动的决策应对市场变化 1.2 订单处理功能分析自动化处理流程订单分配与履行错误检测与处理机制实时订单状态更新订单数…

新能源汽车充电桩常见类型及充电桩站场的智能监管方案

随着新能源汽车市场的迅猛发展&#xff0c;充电桩作为支持其运行的基础设施&#xff0c;也呈现出多样化的类型。这些充电桩不仅在外形和功能上存在差异&#xff0c;更在充电速度、充电方式以及使用场景等方面展现出独特的优势。 一、充电桩类型及区别 1、慢充桩&#xff08;交…

5.vector容器的使用

文章目录 vector容器1.构造函数代码工程运行结果 2.赋值代码工程运行结果 3.容量和大小代码工程运行结果 4.插入和删除代码工程运行结果 5.数据存取工程代码运行结果 6.互换容器代码工程运行结果 7.预留空间代码工程运行结果 vector容器 1.构造函数 /*1.默认构造-无参构造*/ …