当前位置: 首页 > news >正文

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

  1. 根据二叉树创建字符串

在这里插入图片描述

class Solution {
public:/** ()的省略有两种情况* 1.左右都为空,省略* 2.左子树不为空,右子树为空,省略*/string tree2str(TreeNode* root){string s;if(root == nullptr){return s;}s += to_string(root->val);if(root->left){s += "(";s += tree2str(root->left);s +=")";}else if(root->right) // 为了应对左为空,右不为空的情况{s += "()";}if(root->right){s += "(";s += tree2str(root->right);s += ")";}return s;}
};
  1. 二叉树的层序遍历
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root){vector<vector<int>> vv;queue<TreeNode*> q;int levelSize = 0;if(root == nullptr){return vv;}q.push(root);vector<int> v;while(!q.empty()){v.resize(0);levelSize = q.size();while(levelSize--){if((q.front())->left){q.push((q.front())->left);}if((q.front())->right){q.push((q.front())->right);}v.push_back((q.front())->val);q.pop();}vv.push_back(v);}return vv;}
};
  1. 二叉树的层序遍历 II

只需将正着层序遍历的结果reverse()一下即可。

  1. 二叉树的最近公共祖先

在这里插入图片描述
在这里插入图片描述

class Solution {
public:bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st){if(root == nullptr){return false;}st.push(root);if(root == x){return true;}if(FindPath(root->left, x, st)){return true;}if(FindPath(root->right, x, st)){return true;}st.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){stack<TreeNode*> pPath, qPath;FindPath(root, p, pPath); // 找从根节点root到p的路径FindPath(root, q, qPath); // 找从根节点root到q的路径while(pPath.size() != qPath.size()){if(pPath.size() > qPath.size()){pPath.pop();} else{qPath.pop();}}while(pPath.top() != qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};
  1. 二叉搜索树与双向链表

在这里插入图片描述
在这里插入图片描述

class Solution {
public:void InOrderConvert(TreeNode* cur, TreeNode*& prev){if(cur == nullptr){return;}InOrderConvert(cur->left, prev);// 双向链接cur->left = prev;if(prev){prev->right = cur;}// prev向后移prev = cur;InOrderConvert(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* prev = nullptr;// 中序遍历进行链接InOrderConvert(pRootOfTree, prev);// 找头节点TreeNode* head = pRootOfTree;while(head && head->left){head = head->left;}return head;}
};
  1. 从前序与中序遍历序列构造二叉树

在这里插入图片描述

class Solution {
public:TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend){// 子树区间确认是否继续递归创建子树if(inbegin > inend)return nullptr;// 前序创建树TreeNode* root = new TreeNode(preorder[prei++]);// 中序分割左右子树int ini = inbegin;while(ini <= inend){if(inorder[ini] == root->val)break;else++ini;}root->left = _buildTree(preorder, inorder, prei, inbegin, ini - 1);root->right = _buildTree(preorder, inorder, prei, ini + 1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){int i = 0;return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);}
};
  1. 从中序与后序遍历序列构造二叉树
class Solution {
public:TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posti, int inbegin, int inend){if(inbegin > inend)return nullptr;TreeNode* root = new TreeNode(postorder[posti--]);int ini = inbegin;while(ini <= inend){if(inorder[ini] == root->val)break;else++ini;}root->right = _buildTree(inorder, postorder, posti, ini + 1, inend);root->left = _buildTree(inorder, postorder, posti, inbegin, ini - 1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){int i = postorder.size() - 1;return _buildTree(inorder, postorder, i, 0, inorder.size() - 1);}
};

相关文章:

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

根据二叉树创建字符串 class Solution { public:/** ()的省略有两种情况* 1.左右都为空&#xff0c;省略* 2.左子树不为空&#xff0c;右子树为空&#xff0c;省略*/string tree2str(TreeNode* root){string s;if(root nullptr){return s;}s to_string(root->val);if(root…...

有效的数独

有效的数独 题目: 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。示例 1&#xff1a; 输…...

Vue导航守卫beforeRouteEnter,beforeRouteUpdate,beforeRouteLeave

Vue导航守卫以我自己的理解就是监听页面进入,修改,和离开的功能。每个守卫接受三个参数 to: Route: 即将要进入的目标路由对象 from: Route: 当前导航正要离开的路由 next: Function: 一定要调用该方法来 resolve 这个钩子。执行效果依赖 next 方法的调用参数。 next(): 进行…...

小红书《乡村振兴战略下传统村落文化旅游设计》中南大许少辉八一新著

小红书《乡村振兴战略下传统村落文化旅游设计》中南大许少辉八一新著...

Android13 下拉菜单栏中添加快捷截图按钮

Android 13 原生系统下拉状态栏中是没有快捷截图按钮,现在需要添加快捷截图功能。 添加快捷截图功能后的效果图: 涉及修改的文件如下: modified: vendor/mediatek/proprietary/packages/apps/SystemUI/res/values/config.xml modified: vendor/mediatek/proprietary/…...

GFS文件系统

GFS 分布式文件系统 GlusterFS简介 GlusterFS 是一个开源的分布式文件系统。 由存储服务器、客户端以及NFS/Samba 存储网关&#xff08;可选&#xff0c;根据需要选择使用&#xff09;组成。 没有元数据服务器组件&#xff0c;这有助于提升整个系统的性能、可靠性和稳定性。 …...

22 相交链表

相交链表 题解1 快慢双指针改进 (acb bca)题解2 哈希表(偷懒) 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 题目数据 保证 整个链式结构中不存在环。 注意&#xff…...

简历(快速上手)

简历 文章目录 简历简历模板:排版上:内容上:沟通上: 简历在面试中起到关键作用 网申,HR只会花10秒多来看一下 内推,如果简历没优势就只能pass 简历模板: ⽊及简历&#xff08;推荐! &#xff09; &#xff1a; https://resume.mdedit.online 排版上: 尽量简洁&#xff0c;…...

wpf复制xaml及其cs窗体到其他项目 添加现有项,选 .xaml.cs,点添加即可。VS2022

添加现有项&#xff0c;选 LoadingWindow.xaml.cs&#xff0c;点添加即可。...

在线旅游平台步入新时代,携程如何走出自己的路?

今年旅游从线下到线上全方位火了。有统计数据&#xff0c;一季度&#xff0c;光是抖音&#xff0c;旅游达人发布视频数量就高达175万条&#xff0c;播放量1350亿次&#xff0c;收获27亿次点赞。在这一趋势下&#xff0c;许多“不出名”的景区和酒店借势抖音达人完成“出圈”。短…...

java中feign远程调用底层是用Hystrix作为熔断器吗?

在较新的版本中&#xff0c;Feign 默认使用 OpenFeign 作为远程调用的底层实现&#xff0c;并且集成了 Netflix Hystrix 作为熔断器。然而&#xff0c;需要注意的是&#xff0c;自 Feign 10.x 版本开始&#xff0c;默认已不再集成 Hystrix。 在 Feign 中&#xff0c;Hystrix 被…...

Web安全——穷举爆破下篇(仅供学习)

Web安全 一、常见的端口服务穷举1、hydra 密码穷举工具的使用2、使用 hydra 穷举 ssh 服务3、使用 hydra 穷举 ftp 服务4、使用 hydra 穷举 mysql 服务5、使用 hydra 穷举 smb 服务6、使用 hydra 穷举 http 服务7、使用 hydra 穷举 pop3 服务8、使用 hydra 穷举 rdp 服务9、使用…...

强大的JTAG边界扫描(5):FPGA边界扫描应用

文章目录 1. 获取芯片的BSDL文件2. 硬件连接3. 边界扫描测试4. 总结 上一篇文章&#xff0c;介绍了基于STM32F103的JTAG边界扫描应用&#xff0c;演示了TopJTAG Probe软件的应用&#xff0c;以及边界扫描的基本功能。本文介绍基于Xilinx FPGA的边界扫描应用&#xff0c;两者几乎…...

苍穹外卖集成 Apache POI Java实现Excel文件的读写下载

苍穹外卖 day12 Echats 营业台数据可视化整合_软工菜鸡的博客-CSDN博客 Apache POI - the Java API for Microsoft Documents Project News 16 September 2022 - POI 5.2.3 available The Apache POI team is pleased to announce the release of 5.2.3. Several dependencies …...

iOS逆向:工具安装

二〇二三年〇八月二十三日&#xff08;2023版&#xff0c;iOS逆向笔记&#xff09; 对其他APP的实现感兴趣&#xff0c;对技术报以热枕&#xff0c;不去做违反职业道德和违法乱纪的事情&#xff0c;欢迎来到iOS逆向。 工欲善其事必先利其器 ------我说的。 网络不好可配置DNS 1…...

十种数据库缓存相关的技术和机制

数据库的缓存 -- 通过将数据库中的数据或结果集保存在内存或其他快速访问的介质中&#xff0c;能够加快查询响应&#xff0c;减少对磁盘或远程服务器的访问&#xff0c;降低资源消耗。 根据缓存的位置、内容、粒度、更新方式等不同&#xff0c;数据库缓存技术有多种类型和策略。…...

【C++】封装unordered_map和unordered_set(用哈希桶实现)

前言&#xff1a; 前面我们学习了unordered_map和unordered_set容器&#xff0c;比较了他们和map、set的查找效率&#xff0c;我们发现他们的效率比map、set高&#xff0c;进而我们研究他们的底层是由哈希实现。哈希是一种直接映射的方式&#xff0c;所以查找的效率很快…...

面试问题回忆

&#xff08;1&#xff09;查看端口 lsof -i:8080 / netstat lsof -i:8080&#xff1a;查看8080端口占用 lsof abc.txt&#xff1a;显示开启文件abc.txt的进程 lsof -c abc&#xff1a;显示abc进程现在打开的文件 lsof -c -p 1234&#xff1a;列出进程号为1234的进程所打开…...

更多场景、更多选择,Milvus 新消息队列 NATS 了解一下

在 Milvus 的云原生架构中&#xff0c;消息队列&#xff08;Log Broker&#xff09;可谓任重道远&#xff0c;它不仅要具备流式数据持久性、支持 TT 同步、事件通知等能力&#xff0c;还要确保工作节点从系统崩溃中恢复时增量数据的完整性。 在 Milvus 的架构中&#xff0c;一切…...

如何通过python实现一个web自动化测试框架?

要实现一个web自动化测试框架&#xff0c;可以使用Python中的Selenium库&#xff0c;它是最流行的Web应用程序测试框架之一。以下是一个基本的PythonSelenium测试框架的示例&#xff1a; 1、安装Selenium 在终端中输入以下命令&#xff0c;使用 pip 安装 Selenium&#xff1a…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统

核心速览 研究背景 ​​研究问题​​&#xff1a;这篇文章要解决的问题是当前大型语言模型&#xff08;LLMs&#xff09;在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色&#xff0c;但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成&#xff08;RA…...

若依项目部署--传统架构--未完待续

若依项目介绍 项目源码获取 #Git工具下载 dnf -y install git #若依项目获取 git clone https://gitee.com/y_project/RuoYi-Vue.git项目背景 随着企业信息化需求的增加&#xff0c;传统开发模式存在效率低&#xff0c;重复劳动多等问题。若依项目通过整合主流技术框架&…...