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

c++--二叉树应用

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

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。

空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

来源:力扣(LeetCode)

class Solution {
public:string tree2str(TreeNode* root) {//根据前序遍历确定字符串if(root==nullptr)return "";string tree=to_string(root->val);//只有左右子树都为空不保留括号,其他情况都保留括号if(root->left||root->right){tree+='(';tree+=tree2str(root->left);tree+=')'; }if(root->right){tree+='(';tree+=tree2str(root->right);tree+=')'; }return tree;}
};

2.二叉树分层遍历 力扣

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

来源:力扣(LeetCode)

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {//用队列来确定queue<TreeNode*> TreeNode1;vector<vector<int>> vv;int levesize=0;if(root){TreeNode1.push(root);levesize=1;}while(!TreeNode1.empty()){vector<int> v;for(int i=0;i<levesize;i++){TreeNode* front= TreeNode1.front();TreeNode1.pop();v.push_back(front->val);if(front->left){ TreeNode1.push(front->left);}if(front->right){TreeNode1.push(front->right);}}vv.push_back(v);//TreeNode.pop();levesize=TreeNode1.size();}return vv;}
};

3.二叉树的最近公共祖先 力扣

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

来源:力扣(LeetCode)

class Solution {
public:bool find_node(TreeNode* root, TreeNode* p, stack<TreeNode*>& path){if(root==nullptr)return false;path.push(root);if (root == p)return true;if( find_node(root->left, p, path))return true;if( find_node(root->right, p, path))return true;path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){//使用两个栈存放二叉树要找的数据,stack<TreeNode*> ppath;stack<TreeNode*> qpath;find_node(root, p, ppath);find_node(root, q, qpath);//确定长度while (ppath.size() > qpath.size()){ppath.pop();}while (ppath.size() < qpath.size()){qpath.pop();}while (ppath.size() == qpath.size()){if (ppath.top() == qpath.top()){return ppath.top();}ppath.pop();qpath.pop();}return nullptr;}
};

4.  二叉搜索树与双向链表_牛客题霸_牛客网

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围:输入二叉树的节点数 0≤n≤10000≤n≤1000,二叉树中每个节点的值 0≤val≤10000≤val≤1000
要求:空间复杂度O(1)O(1)(即在原树上操作),时间复杂度 O(n)O(n)

注意:

1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构

4.你不用输出双向链表,程序会根据你的返回值自动打印输出

输入描述:

二叉树的根节点

返回值描述:

双向链表的其中一个头节点。

示例1

输入:

{10,6,14,4,8,12,16}
返回值:
From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
class Solution {void Indor(TreeNode* cur,TreeNode*& prev){//确定双向链表if(cur==nullptr)return;Indor(cur->left,prev);cur->left=prev;if(prev)prev->right=cur;prev=cur;Indor(cur->right,prev);}
public:TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* prev=nullptr;Indor(pRootOfTree,prev);//判断头结点TreeNode* head=pRootOfTree;while(head&&head->left){head=head->left;}return head;}
};

5.从前序与中序确定二叉树 力扣

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

来源:力扣(LeetCode)

class Solution {TreeNode* buildTree(vector<int>& preorder,vector<int>& inorder,int& prie,int inbegin,int inend){if(inbegin>inend)//结束条件return nullptr;TreeNode* root=new TreeNode(preorder[prie]);int rooti=inbegin;while(rooti<=inend){if(preorder[prie]==inorder[rooti])break;rooti++;} ++prie;root->left=buildTree(preorder,inorder,prie,inbegin,rooti-1);root->right=buildTree(preorder,inorder,prie,rooti+1,inend);return root;}public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;TreeNode* root=buildTree(preorder,inorder,i,0,inorder.size()-1);return root;}
};

6.中序与后序确定二叉树  力扣

class Solution {TreeNode* _buildTree(vector<int>& inorder,vector<int>& postorder,int& n,int inbegin,int inend){if(inbegin>inend)return nullptr;TreeNode* root=new TreeNode(postorder[n]);int rooti=inbegin;while(rooti<=inend){if(postorder[n]==inorder[rooti])break;rooti++;}n--;root->right=_buildTree(inorder,postorder,n,rooti+1,inend);//先右再左root->left=_buildTree(inorder,postorder,n,inbegin,rooti-1);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n=postorder.size()-1;return _buildTree(inorder,postorder,n,0,postorder.size()-1);}
};

7.二叉树后序遍历迭代算法  力扣

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

示例 1:

输入:root = [1,null,2,3]
输出:[3,2,1]

来源:力扣(LeetCode)

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> nums;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;st.pop();nums.push_back(top->val);}else{cur=top->right;}}return nums;}
};

相关文章:

c++--二叉树应用

1.根据二叉树创建字符串 力扣 给你二叉树的根节点 root &#xff0c;请你采用前序遍历的方式&#xff0c;将二叉树转化为一个由括号和整数组成的字符串&#xff0c;返回构造出的字符串。 空节点使用一对空括号对 "()" 表示&#xff0c;转化后需要省略所有不影响字符…...

以太网DHCP协议(十)

目录 一、工作原理 二、DHCP报文 2.1 DHCP报文类型 2.2 DHCP报文格式 当网络内部的主机设备数量过多是&#xff0c;IP地址的手动设置是一件非常繁琐的事情。为了实现自动设置IP地址、统一管理IP地址分配&#xff0c;TCPIP协议栈中引入了DHCP协议。 一、工作原理 使用DHCP之…...

企业服务器器中了360后缀勒索病毒怎么解决,勒索病毒解密数据恢复

随着网络威胁的增加&#xff0c;企业服务器成为黑客攻击的目标之一。近期&#xff0c;上海某知名律师事务所的数据库遭到了360后缀的勒索病毒攻击&#xff0c;导致企业服务器内的数据库被360后缀勒索病毒加密。许多重要的数据被锁定无法正常读取&#xff0c;严重影响了企业的正…...

详解Kafka分区机制原理|Kafka 系列 二

Kafka 系列第二篇&#xff0c;详解分区机制原理。为了不错过更新&#xff0c;请大家将本号“设为星标”。 点击上方“后端开发技术”&#xff0c;选择“设为星标” &#xff0c;优质资源及时送达 上一篇文章介绍了 Kafka 的基本概念和术语&#xff0c;里面有个概念是 分区(Part…...

CSS学习记录(基础笔记)

CSS简介: CSS 指的是层叠样式表* (Cascading Style Sheets)&#xff0c;主要用于设置HTML页面的文字内容&#xff08;字体、大小、对齐方式&#xff09;&#xff0c;图片的外形&#xff08;边框&#xff09; CSS 描述了如何在屏幕、纸张或其他媒体上显示 HTML 元素 CSS 节省…...

Chatgpt AI newbing作画,文字生成图 BingImageCreator 二次开发,对接wxbot

开源项目 https://github.com/acheong08/BingImageCreator 获取cookie信息 cookieStore.get("_U").then(result > console.log(result.value)) pip3 install --upgrade BingImageCreator import os import BingImageCreatoros.environ["http_proxy"]…...

PPT忘记密码如何解除?

PPT文件所带有的两种加密方式&#xff0c;打开密码以及修改权限&#xff0c;两种密码在打开文件的时候都会有相应的提示&#xff0c;但不同的是两种加密忘记密码之后是不同的。 如果忘记了打开密码&#xff0c;我们就没办法打开PPT文件了&#xff1b;如果是忘记了修改密码&…...

绘制曲线python

文章目录 import matplotlib.pyplot as plt# 提供的数据 x= [1,1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,2,2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9,3,3.1,3.2,3.3,3.4,3.5,3.6,3.7,3.8,3.9,4,4.1,4.2,4.3,4.4,4.5,4.6,4.7,4.8,4.9,5,5.1,5.2,5.3,5.4,5.5,5.6,5.7,5.8,5.9,6,6.1,6.2…...

CentOs 8 常见问题处理

CentOs 8 常见问题处理 vmware虚拟机新增网卡操作 vmware虚拟机新增网卡操作 [rootcentos ~]# ip add 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00inet 127.0…...

OpenAI将GPT-4设置为ChatGPT Plus付费用户的默认模型

OpenAI最近为ChatGPT引入了一系列新功能&#xff0c;这些更新旨在增强用户体验&#xff0c;提供更多指导和更多的功能。其中最显著的功能之一是将GPT-4设置为ChatGPT Plus付费用户的默认模型&#xff0c;这意味着付费订阅用户无需手动切换到其他公开可用的语言模型&#xff0c;…...

textarea 标签如何创建多行文本输入框?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ textarea 的写法⭐ 代码含义⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、…...

(15)Qt绘图(two)

目录 坐标变换 平移坐标轴 缩放坐标轴 旋转坐标轴 定时器加坐标轴旋转实现动画旋转 transform旋转&#xff08;可设置旋转轴&#xff09; 绕X轴旋转 绕Y轴旋转 绕Z轴旋转 错切 Y轴错切 X轴错切 画家的保存与坐标复原 基本图形绘制 绘制点 绘制线 绘制矩形 普…...

用队列实现栈——数据结构与算法

&#x1f636;‍&#x1f32b;️Take your time ! &#x1f636;‍&#x1f32b;️ &#x1f4a5;个人主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王&#x1f525;&#x1f525;&#x1f525; &#x1f4a5;代码仓库&#xff1a;&#x1f525;&#x1f525;魔…...

Python“牵手”1688商品详情页数据采集方法,1688API接口申请指南

1688详情接口 API 是开放平台提供的一种 API 接口&#xff0c;它可以帮助开发者获取商品的详细信息&#xff0c;包括商品的标题、描述、图片等信息。在电商平台的开发中&#xff0c;详情接口API是非常常用的 API&#xff0c;因此本文将详细介绍详情接口 API 的使用。 一、1688…...

记录第一篇被”华为开发者联盟鸿蒙专区 “收录的文章

记录第一篇被”华为开发者联盟鸿蒙专区 “社区收录的文章。 坚持写作的动力是什么&#xff1f; 是记录、分享&#xff0c;以及更好的思考 。...

jenkins的cicd操作

cicd概念 持续集成&#xff08; Continuous Integration&#xff09; 持续频繁的&#xff08;每天多次&#xff09;将本地代码“集成”到主干分支&#xff0c;并保证主干分支可用 持续交付&#xff08;Continuous Delivery&#xff09; 是持续集成的下一步&#xff0c;持续…...

【C++】异常exception

文章目录 1. C语言中传统的处理错误方法2. C中的异常3. 异常的使用3.1 异常的抛出和捕获3.2 异常的重新抛出3.3 异常安全3.4 异常规范 4. 自定义异常体系5. 异常的优缺点 &#x1f4dd; 个人主页 &#xff1a;超人不会飞)&#x1f4d1; 本文收录专栏&#xff1a;《C的修行之路》…...

2023-08-06力扣今日三题

链接&#xff1a; 剑指 Offer 59 - I. 滑动窗口的最大值 题意&#xff1a; 一个lg长度的数组&#xff0c;一个长度k的滑动窗口&#xff0c;求所有滑动窗口中的最大值 解&#xff1a; 优先队列存储存储下标&#xff0c;数字大的优先&#xff0c;每次判断最大的值是否在范围…...

kubeasz在线安装K8S集群

一、介绍 Kubeasz 是一个基于 Ansible 自动化工具&#xff0c;用于快速部署和管理 Kubernetes 集群的工具。它支持快速部署高可用的 Kubernetes 集群&#xff0c;支持容器化部署&#xff0c;可以方便地扩展集群规模&#xff0c;支持多租户&#xff0c;提供了强大的监控和日志分…...

Vue中实现Web端鼠标横向滑动和触控板滑动效果

系列文章目录 文章目录 系列文章目录前言一、鼠标横向滑动效果二、触控板滑动效果总结 前言 在Web端&#xff0c;我们经常需要实现鼠标横向滑动和触控板滑动的效果&#xff0c;以便在页面中展示横向滑动的内容。本文将介绍如何使用Vue和JavaScript来实现这两种效果&#xff0c…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...