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: 线程共享: 堆 线程私有: 老三样 本地内存,元空间 程序计数器 …...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案
一、延迟敏感行业面临的DDoS攻击新挑战 2025年,金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征: AI驱动的自适应攻击:攻击流量模拟真实用户行为,差异率低至0.5%,传统规则引…...
Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...
