相关二叉树进阶面试题的讲解?看这一篇足矣
引子:我们在之前学过c语言的二叉树,但是c++来做更好!本期要讲的题目如下(其实有点拖欠了,很久之前,就想写这个了,今天终于克服自己的欲望,达成了这个愿望)
1, 二叉树创建字符串

思路:基于前序遍历,考虑括号的是否可删除情况!如果左为空,但是右不为空,则不能删除,否则不能确定原先顺序!其他括号直接删掉
代码:
class Solution {
public:string tree2str(TreeNode* root) {string answer;if(root==nullptr)return answer;answer+=to_string(root->val);if(root->left!=nullptr ||root->right){answer+='(';answer+=tree2str(root->left);answer+=")";}//if(root->right)if(root->right!=nullptr){answer+='(';answer+=tree2str(root->right);answer+=")";}return answer;}
};
2, 二叉树的分层遍历1

思路:借助每一次插入数组size就是每一层的元素个数,每一层数据存储在一个一维顺序表中,
然后利用queue队列来进行临时工具过度
代码:
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> answer;if (root == nullptr) {return answer;}size_t size = 0;queue<TreeNode*> h;if (root) {h.push(root);size = 1;}while (size) {vector<int> c;while (size--) {TreeNode* front = h.front();h.pop();c.push_back(front->val);if (front->left) {h.push(front->left);}if (front->right) {h.push(front->right);}}size = h.size();answer.push_back(c);}return answer;}
};
3, 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

思路:观察特征,发现最近的公共祖先是p,q在二侧,直接进行判断就行
或利用二条路径的相交点就是最近的公共祖先
代码:
class Solution {
public:bool is_intree(TreeNode* root, TreeNode* x) {if (root == nullptr) {return false;}return root == x || is_intree(root->left, x) ||is_intree(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) {return nullptr;}if (root == q || root == p) {return root;}bool qleft = is_intree(root->left, q);bool qright = !qleft;bool pleft = is_intree(root->left, p);bool pright = !pleft;if (qleft && pright || qright && pleft) {return root;} else if (qleft && pleft) {return lowestCommonAncestor(root->left, p, q);} else {return lowestCommonAncestor(root->right, p, q);}}
};
4, 二叉树搜索树转换成排序双向链表

思路:进行遍历的同时修改指向,可以有一个前驱节点,提前知道自己的未来是什么,或知道后面指向那里,再进行left等赋予节点
代码:
class Solution {public:// TreeNode* Left(TreeNode*t)// {// while(t->left)// {// t=t->left;// }// return t;// }void INOrder(TreeNode* cur, TreeNode*& prev) {if (cur == nullptr) {return;}INOrder(cur->left, prev);cur->left = prev;if (prev) {prev->right = cur;}prev = cur;INOrder(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {//TreeNode*head=Left(pRootOfTree);if (pRootOfTree == nullptr) {return nullptr;}TreeNode* prev = nullptr;INOrder(pRootOfTree, prev);TreeNode*head=pRootOfTree;while(head->left){head=head->left;}while(prev!=head){prev=prev->left;}// prev->right=head;// head->left=prev;return prev;}
};
5. 根据一棵树的前序遍历与中序遍历构造二叉树

思路:前序:根左右,中序:左根右;在inoreder里面找根节点,以根节点位置以左是左子树,以右为右子树!递归实现
代码:
class Solution {
public:TreeNode* answer(vector<int>& preorder, vector<int>& inorder, int& t,int lefti, int righti) {if (lefti>righti) {return nullptr;}TreeNode* root = new TreeNode(preorder[t]);int v = lefti;while (v <= righti) {if (inorder[v] == preorder[t]) {break;} else {v++;}}t++;root->left = answer(preorder, inorder, t, lefti, v - 1);root->right = answer(preorder, inorder, t, v + 1, righti);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return answer(preorder, inorder, i, 0, inorder.size() - 1);}
};
6. 二叉树的前序遍历,非递归迭代实现

思路:利用栈的特点,先遍历左节点,在找左节点的右子树或右节点,栈为空或cur=nullptr为结束条件
代码:
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> h;vector<int> answer;TreeNode*cur=root;while(cur || !h.empty()){while(cur){h.push(cur);answer.push_back(cur->val);cur=cur->left;}TreeNode* top=h.top();h.pop();cur=top->right; }return answer;}
};
希望帮到大家,其他的题知识大同小异!
相关文章:
相关二叉树进阶面试题的讲解?看这一篇足矣
引子:我们在之前学过c语言的二叉树,但是c来做更好!本期要讲的题目如下(其实有点拖欠了,很久之前,就想写这个了,今天终于克服自己的欲望,达成了这个愿望) 1, 二叉树创建字…...
Nginx部署前端Vue项目的深度解析
目录 一、准备工作 1.1 开发环境 1.2 服务器环境 1.3 Nginx安装 二、构建Vue项目 三、上传静态文件到服务器 四、配置Nginx 五、测试并重新加载Nginx 六、访问Vue应用 七、高级配置 7.1 启用HTTPS 7.2 启用Gzip压缩 7.3 缓存控制 八、常见问题与解决方案 8.1 40…...
PHP一站式解决方案高级房产系统小程序源码
一站式解决方案,高级房产系统让房产管理更轻松 🏠【开篇:告别繁琐,迎接高效房产管理新时代】🏠 你是否还在为房产管理的繁琐流程而头疼?从房源录入、客户咨询到合同签订、售后服务,每一个环节…...
轻量级模型解读——EfficientNet系列
EfficientNet自2019年谷歌提出以来,经历了三个版本,2019EfficientNet ——> 2020EfficientNet-Lite——> 2021EfficientNetv2 文章目录 1、EfficientNet2、EfficientNetv23、EfficientNet-Lite 对于EfficientNet和EfficientNetv2的解读可见另外两篇…...
深入浅出SRS—RTMP实现
RTMP 直播是 SRS 最典型的使用场景,客户端使用 RTMP 协议向 SRS 推流,使用 RTMP 协议从 SRS 拉流,SRS 作为一个 RTMP 直播服务器实现媒体的转发。同时,RTMP 是 SRS 的中转协议,其他协议之间的互通需要先转为 RTMP&…...
睿赛德科技携手先楫共创RISC-V生态|RT-Thread EtherCAT主从站方案大放异彩
日前,在先楫HPM6E00技术日上,睿赛德科技(RT-Thread)向广大工业用户展示了多年来双方在RISC-V生态领域的合作历程和成果,同时睿赛德科技携手先楫半导体首次推出了基于HPM6800处理器的EtherCAT主站解决方案,吸…...
【Cesium实体创建】
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 Cesium目录 前言一、Cesium二、点 线 实体1.点实体2.线实体 总结 前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不…...
为何一些包的Priority在apt-cache和deb文件当中的不一样
最近遇到一些问题,调查的时候发现是一些包的Priority在apt-cache和deb文件当中的不一样导致的,复现步骤如下: $ apt update $ apt download whiptail $ dpkg-deb -e whiptail_0.52.23-1b1_amd64.deb $ cat control | grep Prio Priority: op…...
CRUD的最佳实践,联动前后端,包含微信小程序,API,HTML等(三)
关说不练假把式,在上一,二篇中介绍了我心目中的CRUD的样子 基于之前的理念,我开发了一个命名为PasteTemplate的项目,这个项目呢后续会转化成项目模板,转化成项目模板后,后续需要开发新的项目就可以基于这…...
nvidia-cuda-tensorrt-cudnn下载网站
tensorrt:https://developer.nvidia.com/tensorrt/download cudnn:https://developer.nvidia.com/rdp/cudnn-archive cuda:https://developer.nvidia.com/cuda-toolkit-archive...
GitLab 是什么?GitLab使用常见问题解答
GitLab 是什么 GitLab是由GitLab Inc.开发,使用MIT许可证的基于网络的Git仓库管理工具开源项目,且具有wiki和issue跟踪功能,使用Git作为代码管理工具,并在此基础上搭建起来的web服务。 GitLab 是由 GitLab Inc.开发,…...
数字时代,寻找新的生意增长点之前要做什么准备?
要做好最基础也最繁复的数据管理。 在竞争日益激烈的快消市场中,企业面临前所未有的挑战与压力。在这种高压环境下,数字化转型不再仅仅是选择,而是企业探索新的业务增长点、保持竞争优势的关键战略。然而,随着企业数字化进程的加…...
使用Python本地搭建http.server文件共享服务并实现公网环境远程访问——“cpolar内网穿透”
前言 本文主要介绍如何在Windows系统电脑上使用python这样的简单程序语言,在自己的电脑上搭建一个共享文件服务器,并通过cpolar创建的公网地址,打造一个可以随时随地远程访问的私人云盘。 数据共享作为和连接作为互联网的基础应用ÿ…...
STM32——Flash闪存
以上部分,主存储器:程序存储器; 启动程序代码:系统存储器; 用户选择字节:选项字节 以下是闪存的管理员,用于擦除和读写的地址 C8T6一共64K,主存储器为64页 以下是整体框图&#x…...
python科学计算:NumPy 数组的高级操作
1 数组的形状变换 NumPy 提供了多种方法来改变数组的形状。这些方法不会改变数组的内容,而是重新组织数据的排列方式。 1.1 reshape() 函数 reshape() 是最常用的形状变换函数,它可以改变数组的形状,前提是变换后的总元素数量与原数组一致…...
【补-网络安全】日常运维(二)终端端口占用排查
文章目录 一、利用ipconfig、netstat 命令行统计二 、策略封禁IP 引言:检查频繁,第一步我们梳理完资产,第二步应该对资产终端进行一个排查,诊断把脉,了解清楚系统的端口占用及开放情况 一、利用ipconfig、netstat 命令行统计 1.先用ipconfig定位该终端的IP地址 2.明确IP地址后…...
设计模式之适配器模式:软件世界的桥梁建筑师
一、什么是适配器模式 适配器模式(Adapter Pattern)是一种结构型设计模式(Structural Pattern),通过将类的接口转换为客户期望的另一个接口,适配器可以让不兼容的两个类一起协同工作。其核心思想是通过一个…...
Java 入门指南:Java 并发编程 —— Fork/Join 框架 实现任务的拆分与合并
Fork/Join Fork/Join 是Java并发编程中的一个框架,用于解决大型任务的并行执行问题。它于 Java 7中引入,旨在简化对多核处理器上可并行执行任务的开发。 Fork/Join 框架基于分治(divide and conquer)的设计思想。它将大型任务划…...
token过期时间分平台(web和app)设置方法
token分平台设置方法 本文介绍了Spring下的登录和鉴权机制的主要方法以及 token认证的主要流程,并介绍在spring中web端和APP端设置不同token过期时间的实现方法。主要基于SpringBootspringSecurityJWT框架实现。 一、应用场景 同一系统的跨平台操作,基于…...
[000-01-008].Seata案例应用
业务说明:这里我们创建三个服务,一个订单服务,一个库存服务,一个账户服务。当用户下单时,会在订单服务中创建一个订单,然后通过远程调用库存服务来扣减下单商品的库存;再通过远程调用账户服务来…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
