Java实现二叉树(下)
1.前言
http://t.csdnimg.cn/lO4S7
在前文我们已经简单的讲解了二叉树的基本概念,本文将讲解具体的实现
2.基本功能的实现
2.1获取树中节点个数
public int size(TreeNode root){if(root==null){return 0;}int ret=size(root.left)+size(root.right)+1;return ret;}public static int nodeSize;public void size2(TreeNode root){if(root==null){return;}nodeSize++;size2(root.left);size2(root.right);}
2.2获取叶子节点的个数
/*** 求叶子节点个数* @param root* @return*/public int getLeafNodeCount(TreeNode root){if(root==null){return 0;}if(root.left==null&&root.right==null){return 1;}return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);}public int leftSize;public void getLeafNodeCount2(TreeNode root){if(root==null){return;}if(root.left==null&&root.right==null){leftSize++;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}
2.3获取第K层节点的个数
/*第k层有几个节点*/public int getKLevelNodeCount(TreeNode root,int k){if(root==null){return 0;}if(k==1){return 1;}return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);}
2.4获取二叉树的高度
public int getHeight(TreeNode root){if(root==null){return 0;}int leftHeight=getHeight(root.left);int rightHeight=getHeight(root.right);return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}
2.5检测值为value的元素是否存在
/**** @param root* @param val* @return*/public TreeNode find(TreeNode root,char val){if(root==null){return null;}if(root.val==val){return root;}TreeNode ret=find(root.left,val);if(ret!=null){return ret;}ret=find(root.right,val);if(ret!=null){return ret;}return null;}
2.6判断一棵树是不是完全二叉树
public boolean isSameTree(TreeNode p,TreeNode q){if(p!=null&&q==null||p==null&&q!=null){return false;}if(p==null&&q==null){return true;}if(p.val!=q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
3.二叉树的应用
在知晓了二叉树相关功能的底层实现之后,我们应用二叉树知识来解答
3.1二叉树遍历
二叉树遍历_牛客题霸_牛客网
根据题目我们可以知道这其实是两个题目,一是创建二叉树,二是中序遍历结果
所以我们分成两部来完成
先定义二叉树的结构
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}
当不为'#'的时候,我们就创建节点
public static int i = 0;public static TreeNode createTree(String str) {TreeNode root = null;if (str.charAt(i) != '#') {root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);} else {i++;}return root;}
最后,我们进行中序遍历——根左子树-根节点-根右子树的顺序来递归即可
public static void inorder(TreeNode root){if(root==null){return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}
3.2二叉树的层序遍历
. - 力扣(LeetCode)
这题主要是对二叉树的层序遍历,对于层序遍历是如何遍历的,我们在上文已经讲过——从上而下,自左向右依次遍历.
在了解到概念之后,我们就可以进行解答了
我们要对知识进行灵活的应用,这种从上而下,自左向右的逻辑与前面所讲到的栈和队列知识中队列先进先出逻辑类似,所以我们可以用创建队列来解答
1.是否为空,若为空,则返回空列表
2.若不为空,则进入循环判断(当队列为空则跳出循环),创建一个列表来打印每层的结果
3.将每层结果存入ret,最后返回ret即可
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret=new ArrayList<>();if(root==null){return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size=queue.size();List<Integer> list=new ArrayList<>();//每层while(size>0){TreeNode cur=queue.poll();list.add(cur.val);if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}
对二叉树的基础知识讲解就到这里,如果上述内容对您有帮助,希望给个三连谢谢!
相关文章:
Java实现二叉树(下)
1.前言 http://t.csdnimg.cn/lO4S7 在前文我们已经简单的讲解了二叉树的基本概念,本文将讲解具体的实现 2.基本功能的实现 2.1获取树中节点个数 public int size(TreeNode root){if(rootnull){return 0;}int retsize(root.left)size(root.right)1;return ret;}p…...
Hello 算法10:搜索
https://www.hello-algo.com/chapter_searching/binary_search/ 二分查找法 给定一个长度为 n的数组 nums ,元素按从小到大的顺序排列,数组不包含重复元素。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素,则返回 -1 。 # 首…...
常见分类算法详解
在机器学习和数据科学的广阔领域中,分类算法是至关重要的一环。它广泛应用于各种场景,如垃圾邮件检测、图像识别、情感分析等。本文将深入剖析几种常见的分类算法,帮助读者理解其原理、优缺点以及应用场景。 一、K近邻算法(K-Nea…...
推送恶意软件的恶意 PowerShell 脚本看起来是人工智能编写的
威胁行为者正在使用 PowerShell 脚本,该脚本可能是在 OpenAI 的 ChatGPT、Google 的 Gemini 或 Microsoft 的 CoPilot 等人工智能系统的帮助下创建的。 攻击者在 3 月份的一次电子邮件活动中使用了该脚本,该活动针对德国的数十个组织来传播 Rhadamanthy…...
微服务之Consul 注册中心介绍以及搭建
一、微服务概述 1.1单体架构 单体架构(monolithic structure):顾名思义,整个项目中所有功能模块都在一个工程中开发;项目部署时需要对所有模块一起编译、打包;项目的架构设计、开发模式都非常简单。 当项…...
MES生产管理系统:私有云、公有云与本地化部署的比较分析
随着信息技术的迅猛发展,云计算作为一种新兴的技术服务模式,已经深入渗透到企业的日常运营中。在众多部署方式中,私有云、公有云和本地化部署是三种最为常见的选择。它们各自具有独特的特点和适用场景,并在不同程度上影响着企业的…...
【core analyzer】core analyzer的介绍和安装详情
目录 🌞1. core和core analyzer的基本概念 🌼1.1 coredump文件 🌼1.2 core analyzer 🌞2. core analyzer的安装详细过程 🌼2.1 方式一 简单但不推荐 🌼2.2 方式二 推荐 🌻2.2.1 安装遇到…...
个人练习之-jenkins
虚拟机环境搭建(买不起服务器 like me) 重点: 0 虚拟机防火墙关闭 systemctl stop firewalld.service systemctl disable firewalld.service 1 (centos7.6)网络配置 (vmware 编辑 -> 虚拟网络编辑器 -> 选择NAT模式 ->NAT设置查看网关) vim /etc/sysconfig/network-sc…...
初探vercel托管项目
文章目录 第一步、注册与登录第二步、本地部署 在个人网站部署的助手vercel,支持 Github部署,只需简单操作,即可发布,方便快捷! 第一步、注册与登录 进入vercel【官网】,在右上角 login on,可登…...
软考 - 系统架构设计师 - 质量属性例题 (2)
问题1: 、 问题 2: 系统架构风险:指架构设计中 ,潜在的,存在问题的架构决策所带来的隐患。 敏感点:指为了实现某个质量属性,一个或多个构件所具有的特性 权衡点:指影响多个质量属性…...
基于Python豆瓣电影数据可视化分析系统的设计与实现
大数据可视化项目——基于Python豆瓣电影数据可视化分析系统的设计与实现 2024最新项目 项目介绍 本项目旨在通过对豆瓣电影数据进行综合分析与可视化展示,构建一个基于Python的大数据可视化系统。通过数据爬取收集、清洗、分析豆瓣电影数据,我们提供了…...
【已开源】基于stm32f103的爬墙小车
基于stm32f103的遥控器无线控制爬墙小车,实现功能为可平衡在竖直墙面上,并进行移动和转向,具有超声波防撞功能。 直接上: 演示视频如:哔哩哔哩】 https://b23.tv/BzVTymO 项目说明: 在这个项目中&…...
PCL 基于马氏距离KMeans点云聚类
文章目录 一、简介二、算法步骤三、代码实现四、实现效果参考资料一、简介 在诸多的聚类方法中,K-Means聚类方法是属于“基于原型的聚类”(也称为原型聚类)的方法,此类方法均是假设聚类结构能通过一组原型刻画,在现实聚类中极为常用。通常情况下,该类算法会先对原型进行初始…...
libVLC 视频窗口上叠加透明窗口
很多时候,我们需要在界面上画一些三角形、文字等之类的东西,我们之需要重写paintEvent方法,比如像这样 void Widget::paintEvent(QPaintEvent *event) 以下就是重写的代码。 void Widget::paintEvent(QPaintEvent *event) {//创建QPainte…...
MySQL基础入门上篇
MySQL基础 介绍 mysql -uroot -p -h127.0.0.1 -P3306项目设计 具备数据库一定的设计能力和操作数据的能力。 数据库设计DDL 定义 操作 显示所有数据库 show databases;创建数据库 create database db02;数据库名唯一,不能重复。 查询是否创建成功 加入一些…...
Docker搭建FFmpeg
FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的完整解决方案。FFmpeg 包含了领先的音视频编解码库libavcodec,可以用于各种视频格式的转换。 应用场景包括: 视频转换:把视频从一种格式转换成另一种格式。视…...
Hudi-ubuntu环境搭建
hudi-ubuntu环境搭建 运行 1.编译Hudi #1.把maven安装包上传到服务器 # 官网下载安装包 https://archive.apache.org/dist/maven/maven-3/ scp -r D:\Users\zh\Desktop\Hudi\compressedPackage\apache-maven-3.6.3-bin.tar.gz zhangheng10.8.4.212:/home/zhangheng/hudi/com…...
Hive进阶Day05
一、HDFS分布式文件存储系统 1-1 HDFS的存储机制 按块(block)存储 hdfs在对文件数据进行存储时,默认是按照128M(包含)大小进行文件数据拆分,将不同拆分的块数据存储在不同datanode服务器上 拆分后的块数据会被分别存储在不同的服…...
ssh爆破服务器的ip-疑似肉鸡
最近发现自己的ssh一直有一些人企图使用ssh暴力破解的方式进行密码破解.就查看了一下,真是网络安全太可怕了. 大家自己的服务器密码还是要设置好,管好,做好最基本的安全措施,不然最后只能沦为肉鸡. ssh登陆日志可以在/var/log下看到,ubuntu的话为auth.log,centos为secure文件 查…...
4.JVM八股
JVM空间划分 线程共享和线程私有 1.7: 线程共享: 堆、方法区 线程私有: 虚拟机栈、本地方法栈、程序计数器 本地内存 1.8: 线程共享: 堆 线程私有: 老三样 本地内存,元空间 程序计数器 …...
内网渗透系列-mimikatz的使用以及后门植入
内网渗透系列-mimikatz的使用以及后门植入 文章目录 内网渗透系列-mimikatz的使用以及后门植入前言mimikatz的使用后门植入 msf永久后门植入 (1)Meterpreter后门:Metsvc(2)Meterpreter后门:Persistence NC后…...
5G网络开通与调测ipv4
要求如下: 1. 勘站规划 1. 【重】首先观察NR频点,完成设备选型 2645--选择N41 3455--选择N78 4725--选择N79 设备选型如下:观察AAU的通道数,最大发射功率;选择N41的选型频段也要选41 2. …...
Spark开窗函数之ROW
Spark 1.5.x版本以后,在Spark SQL和DataFrame中引入了开窗函数,其中比较常用的开窗函数就是row_number 该函数的作用是根据表中字段进行分组,然后根据表中的字段排序;其实就是根据其排序顺序,给组中的每条记录添 加一个序号;且每组的序号都是从1开始,可利用它的这个特性进行分组…...
双向链表的实现(详解)
目录 前言初始化双向链表的结构为双向链表的节点开辟空间头插尾插打印链表尾删头删查找指定位置之后的插入删除pos节点销毁双向链表 前言 链表的分类: 带头 不带头 单向 双向 循环 不循环 一共有 (2 * 2 * 2) 种链表 带头指的是:带有哨兵位节点 哨兵位&a…...
SpringBoot项目中如何使用校验工具
用到hutool提供的校验方法与java提供的校验方法 1. 声明数据 String str "123" String regex "^123456$" Boolean is1_6 mismatch(str, regex);2. 定义校验方法 // 校验是否不符合正则格式 private static boolean mismatch(String str, String rege…...
AI预测小分子与蛋白的相关特征: MegaMolBART, MoFlow,ESM-1, ESM-2
1、小分子:MegaMolBART, MoFlow 1)MegaMolBART https://github.com/NVIDIA/MegaMolBART 基于 SMILES 的小分子药物发现与化学信息学深度学习模型。 2)MoFlow https://github.com/calvin-zcx/moflow 用flow流方式分子生成 2、蛋白质:ESM-1, ESM-2 https://github.com/fa…...
基于深度学习的花卉检测系统(含PyQt界面)
基于深度学习的花卉检测系统(含PyQt界面) 前言一、数据集1.1 数据集介绍1.2 数据预处理 二、模型搭建三、训练与测试3.1 模型训练3.2 模型测试 四、PyQt界面实现参考资料 前言 本项目是基于swin_transformer深度学习网络模型的花卉检测系统,…...
深度学习图像处理基础工具——opencv 实战信用卡数字识别
任务 信用卡数字识别 穿插之前学的知识点 形态学操作 模板匹配 等 总体流程与方法 1.有一个模板 2 用轮廓检测把模板中数字拿出来 外接矩形(模板和输入图像的大小要一致 )3 一系列预处理操作 问题的解决思路 1.分析准备:准备模板&#…...
【HBase】HBase高性能架构:如何保证大规模数据的高可用性
HBase高性能原理 HBase 能够提供高性能的数据处理能力,主要得益于其设计和架构的几个关键方面。这些设计特点使得 HBase 特别适合于大规模、分布式的环境中进行高效的数据读写操作。以下是 HBase 高性能的主要原因: 1. 基于列的存储 HBase 是一个列式…...
JAVA基础两个项目案例代码
1.JAVA使用ArrayList上架菜品案例 视频参考链接 创建一个Food.java类 package org.example;// 菜品类 public class Food {private String name; // 菜品名private double price; // 价格private String desc; // 菜品描述public Food() {}public Food(String name, Double …...
把wordpress集成进/赣州seo优化
《程序设计与数据结构》第10周学习总结 教材学习内容总结 图中的树问题图中的最短路径问题活动顶点与活动边的问题教材学习中的问题和解决过程 问题1:最短路径算法中的Path列表值不理解问题1解决方案:结对伙伴刘伟康同学为我的解答:各顶点对间…...
网站建设规划大纲/提高工作效率的重要性
目前来说,win8没有本地数据库。使用sqlite作为win8的数据存取是一种比较实在的解决方案。 我在使用sqlite过程中,遇到过一些问题,现在做一个小结作为本次的开发笔记吧。 (1) sqlite在vs2012上的安装教程参考:sqlite for win8. sq…...
创新能力建设资金网站/seo整站优化什么价格
对乔布斯和马斯克访谈的反思: 1、这个世界不在乎你的自尊,只在乎你自我感觉良好的同时有所成就。说明大多数人的观点是《乌合之众》,必须有从想到去做到的能力,面子是无能者维护尊严的盾牌。 2、年轻时候一定要大量阅读࿰…...
三站合一 网站建设/深圳关键词优化公司哪家好
玩python的人大都在linux下进行开发,由于长期习惯在windows下开发代码,今天蛋疼尝试在window7下配置python2.7tornado3.3开发环境,必然的中间遇到各种报错,但是最终还是配置成功了,发帖方便网友少走弯路.开工! 前提: p…...
住建厅报名考试入口/怎样进行seo推广
在Eclipse中写Python代码时,会发现注释颜色很浅,看起来比较费力。根据以下操作可以修改颜色,缓解眼球疲劳。 Window-->Preferences-->Pydev,选中Editor,右边的Appearance color options,选中Common&…...
宝塔 wordpress/seo网络优化
前言 继续学习sqli-labs 本篇是less 23-24 Less-23 GET - Error based - strip comments (基于错误的,过滤注释的GET型) 测试 ?id1然后尝试#、--等注释 都无用 看了眼源码 注释都被替换掉了 尝试闭合 ?id-1 union select 1, 2, 3 ?id-1 union select 1, dat…...