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

初级算法-树

文章目录

        • 二叉树的最大深度
          • 题意:
          • 解:
          • 代码:
        • 验证二叉搜索树
          • 题意:
          • 解:
          • 代码:
        • 对称二叉树
          • 题意:
          • 解:
          • 代码:
        • 二叉树的层序遍历
          • 题意:
          • 解:
          • 代码:
        • 将有序数组转换为二叉搜索树
          • 题意:
          • 解:
          • 代码:

二叉树的最大深度

题意:

如题

解:

简单的树搜索操作,DFS和BFS

代码:
#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
int dfs(TreeNode* root)
{int ans=1;if(root->left!=nullptr) ans=max(ans,1+dfs(root->left));if(root->right!=nullptr) ans=max(ans,1+dfs(root->right));return ans;
}
int bfs(TreeNode* root)
{int n=0;queue<TreeNode*>q;q.push(root);while(true){queue<TreeNode*>temp;while(!q.empty()){TreeNode* nn=q.front();q.pop();if(nn->left!=nullptr) temp.push(nn->left);if(nn->right!=nullptr) temp.push(nn->right);}q=temp;n++;if(q.empty()) break;}return n;
}
int maxDepth(TreeNode* root)
{if(root==nullptr) return 0;int ans1=dfs(root);cout<<"ans1:"<<ans1<<endl;int ans2=bfs(root);cout<<"ans2:"<<ans2<<endl;return ans1;
}
int main()
{}

验证二叉搜索树

题意:

一个二叉搜索树,要求有效条件:左子树严格小于父节点,右子树严格大于父节点且,且子节点的子树也要尊称这个条件

解:

dfs标记区间,蛮好写的

中序遍历,二叉搜索树的中序遍历是递增的,,很有趣

代码:
#include<iostream>
#include<climits>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
bool zxbl(TreeNode* root,long long &val)//longlong 中序遍历
{bool ans=true;if(root->left!=nullptr) ans&=zxbl(root->left,val);if(root->val>val) val=root->val;else ans=false;if(root->right!=nullptr) ans&=zxbl(root->right,val);return ans;
}
bool dfs(TreeNode* root,long long l,long long r)//longlong dfs 
{bool ans=true;if(root->val<=l || root->val>=r) return false;if(root->left!=nullptr){ans=dfs(root->left,l,root->val);if(!ans) return ans;}if(root->right!=nullptr){ans=dfs(root->right,root->val,r);if(!ans) return ans;}return ans;
}
bool isValidBST(TreeNode* root)
{//long long l=(long long)INT_MIN-1,r=(long long)INT_MAX+1;long long temp=(long long)INT_MIN-1;//bool ans=dfs(root,l,r);bool ans=zxbl(root,temp);cout<<ans<<endl;return ans;
}
int main()
{}

对称二叉树

题意:

一个二叉树判断是否对称

解:

成对访问就行

代码:
#include<bits/stdc++.h>
#include<climits> 
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
bool dfs(TreeNode* root1,TreeNode* root2)//dfs 递归 
{bool ans=true;if(root1==nullptr||root2==nullptr) return false;if(root1->val!=root2->val) return false;if(root1->left!=nullptr||root2->right!=nullptr) ans&=dfs(root1->left,root2->right);if(root1->right!=nullptr||root2->left!=nullptr) ans&=dfs(root1->right,root2->left);return ans;
}
typedef pair<TreeNode*,TreeNode*>PTT;
bool isSymmetric(TreeNode* root)//迭代 
{bool ans=true;PTT ptt;queue<PTT>PTT_q;PTT_q.push({root,root});while(true){queue<PTT>PTT_temp;while(!PTT_q.empty()){ptt=PTT_q.front();PTT_q.pop();if(ptt.first==nullptr||ptt.second==nullptr){ans=false;break;}if(ptt.first->val!=ptt.second->val){ans=false;break;}if(ptt.first->left!=nullptr||ptt.second->right!=nullptr) PTT_temp.push({ptt.first->left,ptt.second->right});if(ptt.first->right!=nullptr||ptt.second->left!=nullptr) PTT_temp.push({ptt.first->right,ptt.second->left});}PTT_q=PTT_temp;if(!ans||PTT_q.empty()) break;}return ans;
}
/*
bool isSymmetric(TreeNode* root)
{bool ans=dfs(root,root);cout<<ans<<endl;return ans;
}*/
int main()
{}

二叉树的层序遍历

题意:

如题

解:

BFS板子

代码:
#include<bits/stdc++.h>
#include<climits> 
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
vector<vector<int>> levelOrder(TreeNode* root)
{vector<vector<int>>ans;if(root==nullptr) return ans;queue<TreeNode*>q;q.push(root);while(true){vector<int>an;queue<TreeNode*>next;while(!q.empty()){TreeNode* temp=q.front();q.pop();an.push_back(temp->val);if(temp->left!=nullptr) next.push(temp->left);if(temp->right!=nullptr) next.push(temp->right);}ans.push_back(an);q=next;if(q.empty())break;}return ans;
}
int main()
{}

将有序数组转换为二叉搜索树

题意:

如题,需要转换成高度平衡二叉树

解:

建搜索二叉树板子add+高度平衡思维ph

为了让高度平衡,左右两边子节点数量差要小于等于1,所以每次从有序数组中取中间,然后对左右区间再建树

代码:
#include<bits/stdc++.h>
#include<climits> 
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
void add(TreeNode* node,int &nums)
{if(node->val==nums) return;if(node->val>nums){if(node->left!=nullptr) add(node->left,nums);else node->left=new TreeNode(nums);}if(node->val<nums){if(node->right!=nullptr) add(node->right,nums);else node->right=new TreeNode(nums);}
}
void ph(TreeNode* &node,int l,int r,vector<int>& nums)
{if(l>r) return;int mid=(l+r)>>1;if(node==nullptr) node=new TreeNode(nums[mid]);else{cout<<"add:"<<nums[mid]<<endl;add(node,nums[mid]);}ph(node,l,mid-1,nums);ph(node,mid+1,r,nums);
}
TreeNode* sortedArrayToBST(vector<int>& nums)
{int lg=nums.size();TreeNode* root=nullptr;ph(root,0,lg-1,nums);return root;
}
int main()
{}

相关文章:

初级算法-树

文章目录 二叉树的最大深度题意&#xff1a;解&#xff1a;代码&#xff1a; 验证二叉搜索树题意&#xff1a;解&#xff1a;代码&#xff1a; 对称二叉树题意&#xff1a;解&#xff1a;代码&#xff1a; 二叉树的层序遍历题意&#xff1a;解&#xff1a;代码&#xff1a; 将有…...

Harbor Failed to start docker.service: Unit docker.service not found.

有可能是修改配置文件导致了问题&#xff0c;最近肯定修改过某个配置文件 本文只针对配置Harbor过程中遇到该问题&#xff0c;很有是deamon.json的 insecure-registries和docker.service的 ExecStart/usr/bin/dockerd --insecure-registry冲突了&#xff0c;删掉一个就好 我使…...

网络安全/信息安全(黑客技术)自学笔记

一、网络安全基础知识 1.计算机基础知识 了解了计算机的硬件、软件、操作系统和网络结构等基础知识&#xff0c;可以帮助您更好地理解网络安全的概念和技术。 2.网络基础知识 了解了网络的结构、协议、服务和安全问题&#xff0c;可以帮助您更好地解决网络安全的原理和技术…...

ADB 命令结合 monkey 的简单使用,超详细

一&#xff1a;ADB简介 1&#xff0c;什么是adb&#xff1a; ADB 全称为 Android Debug Bridge&#xff0c;起到调试桥的作用&#xff0c;是一个客户端-服务器端程序。其中客户端是用来操作的电脑&#xff0c;服务端是 Android 设备。ADB 也是 Android SDK 中的一个工具&…...

级联选择框

文章目录 实现级联选择框效果图实现前端工具版本添加依赖main.js导入依赖级联选择框样式 后端数据库设计 实现级联选择框 效果图 实现 前端 工具版本 node.js v16.6.0vue3 级联选择框使用 Element-Plus 实现 添加依赖 在 package.json 添加依赖&#xff0c;并 npm i 导入…...

如何在3ds max中创建可用于真人场景的巨型机器人:第 5 部分

推荐&#xff1a; NSDT场景编辑器助你快速搭建可二次开发的3D应用场景 1. After Effects 中的项目设置 步骤 1 打开“后效”。 打开后效果 步骤 2 我有真人版 我在After Effects中导入的素材。这是将 用作与机器人动画合成的背景素材。 实景镜头 步骤 3 有背景 选定的素材…...

【MATLAB第61期】基于MATLAB的GMM高斯混合模型回归数据预测

【MATLAB第61期】基于MATLAB的GMM高斯混合模型回归数据预测 高斯混合模型GMM广泛应用于数据挖掘、模式识别、机器学习和统计分析。其中&#xff0c;它们的参数通常由最大似然和EM算法确定。关键思想是使用高斯混合模型对数据&#xff08;包括输入和输出&#xff09;的联合概率…...

Mnist分类与气温预测任务

目录 传统机器学习与深度学习的特征工程特征向量pytorch实现minist代码解析归一化损失函数计算图Mnist分类获取Mnist数据集&#xff0c;预处理&#xff0c;输出一张图像面向工具包编程使用TensorDataset和DataLoader来简化数据预处理计算验证集准确率 气温预测回归构建神经网络…...

Pytorch深度学习-----神经网络的卷积操作

系列文章目录 PyTorch深度学习——Anaconda和PyTorch安装 Pytorch深度学习-----数据模块Dataset类 Pytorch深度学习------TensorBoard的使用 Pytorch深度学习------Torchvision中Transforms的使用&#xff08;ToTensor&#xff0c;Normalize&#xff0c;Resize &#xff0c;Co…...

微信小程序转抖音小程序的坑:The component <xxx> used in pages/xxx/xxx is undefined

微信小程序组件定义在根目录的 app.json 中了&#xff0c;在抖音小程序中出现找不到的情况。 在需要用到组件的 pages 目录中页面文件夹的 json "usingComponents": {} 大括号中添加页面使用的组件&#xff0c;即可使用......

Vue+element Ui的el-select同时获取value和label的方法总结

1.通过ref的形式&#xff08;推荐) <template><div class"root"><el-selectref"optionRef"change"handleChange"v-model"value"placeholder"请选择"style"width: 250px"><el-optionv-for&q…...

乐划锁屏充分发挥强创新能力,打造内容业新生态

乐划锁屏作为新型内容媒体,在这一市场有着众多独特的优势,不仅能够通过多场景的联动给内容创作者带来了更多可能性,还促进了更多优质作品的诞生,为用户带来更加丰富多彩的锁屏使用体验。 作为OPPO系统原生的OS应用,乐划锁屏一直致力于打造为用户提供至美内容的内容平台,吸引了全…...

防御第三天

1.总结当堂NAT与双机热备原理&#xff0c;形成思维导图 2.完成课堂NAT与双机热备实验 fw1: <USG6000V1>sy [USG6000V1]int g0/0/0 [USG6000V1-GigabitEthernet0/0/0]ip add 192.168.18.2 24 [USG6000V1-GigabitEthernet0/0/0]service-manage all permit (地址无所谓&…...

用JavaScript和HTML实现一个精美的计算器

文章目录 一、前言二、技术栈三、功能实现3.1 引入样式3.2 编写显示页面3.2 美化计算器页面3.3 实现计算器逻辑 四、总结 一、前言 计算器是我们日常生活中经常使用的工具之一&#xff0c;可以帮助我们进行简单的数学运算。在本博文中&#xff0c;我将使用JavaScript编写一个漂…...

基于postgresl的gaussDB(DWS)地址省市区解析函数

地址格式为&#xff1a; 省(自治区&#xff0c;直辖市)、市、区。 直辖市的地址格式为&#xff0c; 北京市北京市海淀区xxxxx。 若是北京市海淀区xxx&#xff0c;自己改改就可以了 采用的是笨办法&#xff0c;穷举。 涉及的两个主要内置函数。 1. instr( <start_positio…...

【Golang】Golang进阶系列教程--Go 语言 new 和 make 关键字的区别

文章目录 前言new源码使用 make源码使用 总结 前言 本篇文章来介绍一道非常常见的面试题&#xff0c;到底有多常见呢&#xff1f;可能很多面试的开场白就是由此开始的。那就是 new 和 make 这两个内置函数的区别。 在 Go 语言中&#xff0c;有两个比较雷同的内置函数&#xf…...

Day 9 C++ 内存分区模型

目录 内存四区 代码区 全局区 栈区 堆区 内存四区意义&#xff1a; 程序运行前后内存变化 程序运行前 代码区 全局区 程序运行后 栈区 堆区 new操作符 基本语法 创建 释放&#xff08;delete&#xff09; 内存四区 代码区 代码区&#xff08;Code Segment&…...

STM32 CubeMX 定时器(普通模式和PWM模式)

STM32 CubeMX STM32 CubeMX 定时器&#xff08;普通模式和PWM模式&#xff09; STM32 CubeMXSTM32 CubeMX 普通模式一、STM32 CubeMX 设置二、代码部分STM32 CubeMX PWM模式一、STM32 CubeMX 设置二、代码部分总结 STM32 CubeMX 普通模式 一、STM32 CubeMX 设置 二、代码部分 …...

mysql清除主从复制关系

mysql清除主从复制关系 mysql主从复制中,需要将主从复制关系清除,需要取消其从库角色。这可通过执行RESET SLAVE ALL清除从库的同步复制信息、包括连接信息和二进制文件名、位置。从库上执行这个命令后,使用show slave status将不会有输出。reset slave是各版本Mysql都有的功…...

Spring Cloud Eureka 服务注册和服务发现超详细(附加--源码实现案例--及实现逻辑图)

文章目录 EurekaEureka组件可以实现哪些功能什么是CAP原则&#xff1f;服务注册代码实战搭建注册中心服务A搭建服务B搭建启动服务启动注册中心启动服务A启动服务B 结束语 Eureka 这篇文章先讲述一下Eureka的应用场景、代码实现案例&#xff0c;多个服务模块注册到Euraka中&…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...