【C++二叉树】进阶OJ题

【C++二叉树】进阶OJ题

目录

  • 【C++二叉树】进阶OJ题
      • 1.二叉树的层序遍历II
        • 示例代码
        • 解题思路
      • 2.二叉搜索树与双向链表
        • 示例代码
        • 解题思路
      • 3.从前序与中序遍历序列构造二叉树
        • 示例代码
        • 解题思路
      • 4.从中序与后序遍历序列构造二叉树
        • 示例代码
        • 解题思路
      • 5.二叉树的前序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路
      • 6.二叉树的中序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路
      • 7二叉树的后序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路

作者:爱写代码的刚子

时间:2023.9.6

前言:本篇博客总结了一些二叉树有关的一些中等难度OJ题,总结这些题的解题思路


1.二叉树的层序遍历II

题目链接

示例代码

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(!root){return vv;}queue<TreeNode*> q;q.push(root);while(!q.empty()){int curlevel = q.size();vv.push_back(vector<int> ());while(curlevel--){TreeNode *front=q.front();vv.back().push_back(front->val);q.pop();if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}}reverse(vv.begin(),vv.end());return vv;}
};

解题思路

  1. 选择使用队列来实现

  2. 在这里插入图片描述

  3. 注意这里使用变量curlevel来记录每层的元素个数,并且第二个while循环中需要curlevel来计数,因为题目中要求返回 vector<vector>,所以记录每层的元素个数是必要的。

  4. 由于题目要求返回自底向上的层序遍历,所以我们还需要reverse函数将vector<vector>容器进行反转。

2.二叉搜索树与双向链表

题目链接

示例代码

class Solution {
public:void test(TreeNode* cur,TreeNode*& prev){if(cur==nullptr){return;}test(cur->left,prev);cur->left=prev;if(prev)//注意prev可能为nullptr{prev->right=cur;}prev=cur;test(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode*prev=nullptr;test(pRootOfTree,prev);TreeNode* leftover=pRootOfTree;while(leftover&&leftover->left){leftover=leftover->left;}return leftover;}
};

解题思路

  1. 采用中序遍历
  2. 由于二叉树遍历的特殊性,我们无法找到下一个遍历的对象,所以我们设立新旧指针:cur和prev,由于根节点prev未知,所以我们传入nullptr
  3. 我们让cur指针先走,对旧节点的指针朝向进行修改(prev的left和right指针)
  4. 如图:在这里插入图片描述

本质其实就是让cur先走,记录先前节点(prev),并修改先前节点的指针朝向。

3.从前序与中序遍历序列构造二叉树

题目链接

示例代码

class Solution {
public:TreeNode* test(vector<int>& preorder, vector<int>& inorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode* root=new TreeNode(preorder[prei]);int rooti=begini;while(rooti<=endi){if(preorder[prei]==inorder[rooti]){break;}else{++rooti;}}++prei;root->left=test(preorder, inorder,begini,prei,rooti-1);root->right=test(preorder, inorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return test(preorder,inorder,0,i,preorder.size()-1);}
};

解题思路

  1. 前序遍历可以确定根节点的位置

  2. 确定了根再去中序遍历里找到对应的根

  3. 两者遍历的图示:在这里插入图片描述

  4. 观察图示结构,我们可以将前序遍历中的数据从左到右进行遍历,一次将遍历的节点作为根节点

  5. 观察图示结构,我们利用前序遍历中定的根节点在中序遍历中找到对应的位置,用中序遍历的结构来进行递归(类似分治)

  6. 递归的结束条件就是递归到子叶节点时,子叶节点再进行递归,递归区间有误。(begini>endi)

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

题目链接

示例代码

class Solution {
public:TreeNode*test(vector<int>& inorder, vector<int>& postorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode*root=new TreeNode(postorder[prei]);int rooti=endi;while(rooti>=begini){if(inorder[rooti]==postorder[prei]){break;}--rooti;}--prei;root->right=test(inorder, postorder,rooti+1,prei,endi);root->left=test(inorder, postorder,begini,prei,rooti-1);//root->right=test(inorder, postorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;return test(inorder, postorder,0,i,i);}
};

解题思路

  1. 思路与《从中序与后序遍历序列构造二叉树》类似,先画图:在这里插入图片描述

  2. 我们发现与《从中序与后序遍历序列构造二叉树》这道题中的结构类似,所以考虑后序遍历序列从右往左遍历,依次将访问的节点作为根节点

  3. 注意!后序遍历中访问完根节点后访问的是右节点,所以我们应先构造右子树,将《从中序与后序遍历序列构造二叉树》题中的示例代码中两个递归入口交换顺序即可

5.二叉树的前序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* tmp=root;while(tmp||!st.empty()){while(tmp){v.push_back(tmp->val);st.push(tmp);tmp=tmp->left;}tmp=st.top()->right;st.pop();}return v;}
};

解题思路

  1. 使用vector和stack
  2. 先将二叉树最左边的节点push进栈,将节点储存的值push_back进vector
  3. 再取出栈顶元素,控制指针进入栈顶元素节点的右子树,并pop该栈顶元素,重复以上步骤
  4. 图示:在这里插入图片描述

6.二叉树的中序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();v.push_back(top->val);cur=top->right;st.pop();}return v;}
};

解题思路

过程与前序遍历类似,只是访问的时机不同,中序遍历要在所有左子树push进栈后再进行访问,并pop栈顶元素

7二叉树的后序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;TreeNode* prev=nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();if(top->right==nullptr||top->right==prev){prev=top;v.push_back(top->val);st.pop();}else{cur=top->right;}}return v;}
};

解题思路

  1. 我们需要设定访问时机,当右子树已经访问完了或者没有右子树时进行访问。
  2. 如何判读右子树是否访问完了:要引入prev指针记录上一个访问的节点,判断prev是否等于当前节点(top)的右子树。
  3. 注意这里使用的是if…else语句,并不是无脑cur=top->right

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

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

相关文章

科技云报道:AI+云计算共生共长,能否解锁下一个高增长空间?

科技云报道原创。 在过去近一年的时间里&#xff0c;AI大模型从最初的框架构建&#xff0c;逐步走到落地阶段。 然而&#xff0c;随着AI大模型深入到千行百业中&#xff0c;市场开始意识到通用大模型虽然功能强大&#xff0c;但似乎并不能完全满足不同企业的个性化需求。 大…

【优选算法】—— 前缀和算法

前言&#xff1a; 本期&#xff0c;我将要带大家学习的是有关前缀和算法的学习&#xff01;&#xff01;&#xff01; 目录 &#xff08;一&#xff09;什么是前缀和算法 &#xff08;二&#xff09;题目讲解 1、【模板】前缀和 2、【模板】二维前缀和 3、 和可被K整除的…

动态内存申请

动态内存申请 静态分配 1、 在程序编译或运行过程中&#xff0c;按事先规定大小分配内存空间的分配方式。int a [10] 2、 必须事先知道所需空间的大小。 3、 分配在栈区或全局变量区&#xff0c;一般以数组的形式。 4、 按计划分配 动态分配 1、在程序运行过程中&#xff0c…

python读取.txt文件中某些关键字后面的内容 并根据该数据画图

感谢一下悦姐帮忙 import re#先把文件读进来&#xff0c;用read读入的是字符串&#xff0c;readlines是list with open(resok.txt) as f:txt f.read()dataset r5low:.*|5mix:.*|5normal:.* para rMAE: (.{6})#意思是MAE&#xff1a; 后面的六个东西 row_data re.findall(d…

【Arduino27】DHT11温湿度传感器模拟值实验

硬件准备 DHT11温湿度&#xff1a;1个 面包板&#xff1a;1个 杜邦线&#xff1a;3根 硬件连线 VDD引脚接 5V 电源 DATE引脚接 4号 接口 GND引脚接 GND 接口 软件程序 #include<DHT.h>#define DHT11_pin 4 //温湿度传感器引脚DHT dht(DHT11_pin,DHT11);float tem…

QuantLib学习笔记——看看几何布朗运动有没有股票走势的感觉

⭐️ 小鹿在乱撞 小伙伴们肯定看过股票的走势&#xff0c;真是上蹿下跳啊&#xff0c;最近小编学了一丢丢关于随机过程和QuantLib的知识&#xff0c;想利用随机过程生成一个类似股票价格走势的图&#xff0c;安排&#xff01;&#xff01;&#xff01; ⭐️ 随机过程 随机过程…

JS中call方法是什么,call()的原理是什么?如何手写一个call()?Symbol是什么,怎么用Symbol调优?含详细解析

&#x1f389;call() &#x1f495;call()的参数 thisArg&#xff1a;在调用 func 时要使用的 this 值 arg1, …, argN &#xff08;可选&#xff09; 函数的参数 ✨call()的描述&#xff1a; 首先声明 func是一个函数&#xff0c;person是一个对象 针对这段代码&#xff1a;f…

Json“牵手”亚马逊商品详情数据方法,亚马逊商品详情API接口,亚马逊API申请指南

亚马逊平台是美国最大的一家网络电子商务公司&#xff0c;亚马逊公司是1995年成立&#xff0c;刚开始只做网上书籍售卖业务&#xff0c;后来扩展到了其他产品。现在已经是全世界商品品种最多的网上零售商和第二互联网公司&#xff0c;亚马逊是北美洲、欧洲等地区的主流购物平台…

【2023最新版】腾讯云CODING平台使用教程(Pycharm/命令:本地项目推送到CODING)

目录 一、CODING简介 网址 二、CODING使用 1. 创建项目 2. 创建代码仓库 三、PyCharm&#xff1a;本地项目推送到CODING 1. 管理远程 2. 提交 3. 推送 4. 结果 四、使用命令推送 1. 打开终端 2. 初始化 Git 仓库 3. 添加远程仓库 4. 添加文件到暂存区 5. 提交更…

OPENCV+QT环境配置

【qtopencv开发入门&#xff1a;4步搞定opencv环境配置2】https://www.bilibili.com/video/BV1f34y1v7t8?vd_source0aeb782d0b9c2e6b0e0cdea3e2121eba 第一步&#xff1a; 安装QT Qt 5.15 第二步&#xff1a; 安装OPENCV VS2022 Opencv4.5.5 C 配置_愿飞翔的鱼儿的博客…

认识doubbo和rpc

开个新坑&#xff0c;和大家一起学习Dubbo 3.X。我们按照一个由浅入深顺序来学习&#xff0c;先从使用Dubbo开始&#xff0c;再深入Dubbo的核心原理。 今天我们就从认识Dubbo开始&#xff0c;整体的内容可以分为3个部分&#xff1a; Dubbo是什么RPC是什么Dubbo的架构 正式开…

uniapp项目实践总结(十一)自定义网络检测组件

导语&#xff1a;很多时候手机设备会突然没网,这时候就需要一个网络检测组件,在没网的时候显示提示用户,提供用户体验。 目录 准备工作原理分析组件实现实战演练案例展示 准备工作 在components新建一个q-online文件夹&#xff0c;并新建一个q-online.vue的组件&#xff1b;…

[刷题记录]牛客面试笔刷TOP101

牛客笔试算法必刷TOP101系列,每日更新中~ 1.合并有序链表2023.9.3 合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com) 题意大致为: 将两个链表中的元素按照从小到大的顺序合并成为一个链表. 所给予的条件: 给出的所要合并的链表都是从小到大顺序排列的. 思路: 创建一…

[Java]异常

目录 1.异常的概念与体系结构 1.1异常的概念 1.1.1算术异常 1.1.2数组越界异常 1.1.3空指针异常 1.2异常的体系结构 1.3异常的分类 2.异常的处理 2.1 防御式编程 2.2异常的抛出 2.3异常的捕获 2.3.1 异常声明throws 将光标放在抛出异常方法上&#xff0c;alt Insert …

SAC算法

SAC算法 全称Soft Actor-Critic算法&#xff0c;为优化目标引入了熵约束项&#xff0c;增大了动作的探索性&#xff0c;避免陷入局部最优解&#xff0c;原论文 继承了Soft Q-Learning提出了Soft Policy Iteration&#xff0c;进而推导了Soft Actor-Critic参数更新时机&#xff…

RCU501 RMP201-8 KONGSBERG 分布式处理单元

RCU501 RMP201-8 KONGSBERG 分布式处理单元 AutoChief600使用直接安装在主机接线盒中的分布式处理单元。进出发动机的所有信号都在双冗余CAN线路(发动机总线)上传输。 所有不重要的传感器都可以与K-Chief 600报警和监控系统共享&#xff0c;只需要一个主机接口。这一原则大大…

Redis之SDS底层原理解读

目录 SDS是什么&#xff1f; SDS结构示例 概述 空间预分配 惰性空间释放 C字符串跟SDS的区别&#xff1f;为什么用SDS&#xff1f; SDS是什么&#xff1f; Redis 底层的程序语言是由 C 语言编写的&#xff0c;C 语言默认字符串则是以空字符结尾的字符数组&#xff08…

【C++】异常

目录 一、概念二、异常的使用1、异常的抛出和捕获2、异常的重新抛出3、异常安全4、异常规范 三、自定义异常体系四、C标准库的异常体系五、异常的优缺点 一、概念 传统的错误处理机制&#xff1a; 终止程序&#xff0c;如assert&#xff0c;缺陷&#xff1a;用户难以接受。如…

Apache Tomcat漏洞复现

文章目录 弱口令启动环境漏洞复现 本地文件包含启动环境漏洞复现 弱口令 启动环境 来到vulhub/tomcat/tomcat8/靶场 cd vulhub/tomcat/tomcat8/安装环境并启动&#xff1a; sudo docker-compose up -d && sudo docker-compose up -d修改端口后启动&#xff1a; su…

十七、MySQL约束演示

1、约束定义 &#xff08;1&#xff09;概念 约束&#xff0c;顾名思义&#xff0c;时作用域表中字段上的规则&#xff0c;用于限制存储在表中的数据&#xff0c;主要用于保证数据库中数据的正确、有效性和完整性。 &#xff08;2&#xff09;各种约束分类 1、非空约束(限制…