当前位置: 首页 > 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…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

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

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

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...