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

java数据结构_二叉树_5.5

2.7 二叉树的相关操作

1. size方法 获取二叉树元素个数

思路:遍历思路,在前面文章中,前序 中序 后序遍历的时候,会把树中的所有结点遍历一次。可以添加一个计数器,遍历一个结点就加一次。

于是有如下代码:

public int size = 0;   //定义一个成员变量size
public int nodeSize(TreeNode root) {if(root == null)  return 0;size++;nodeSize(root.left);nodeSize(root.right);return size;
}

在IDEA中测试符合预期,但还是思考,上面的方法,也没有利用到这个方法的返回值。

换个角度,以子问题的思路来思考:要算当前root总共有多少个结点,其实就等于:当前root结点的左子树的结点个数 + 当前root结点的右子树的结点个数 + 1。

于是有如下代码:

public int nodeSize(TreeNode root) {int size = 0;if(root == null) return size;int leftSize = nodeSize(root.left);int rightSize = nodeSize(root.right);return leftSize + rightSize + 1;
}

该代码仍是化大树为小树,逐个解决子问题过程。

下图为部分递归过程,注意先递出去,再归回来

2. getLeafSize方法 得到二叉树叶子结点个数

先回忆概念,叶子结点也就是度为0的结点,也就是左右子树均为null的结点

于是有如下代码:

public int leaveSize = 0;public int getLeaveSize(TreeNode root) {if(root == null) return leaveSize;if(root.left == null && root.right == null) {leaveSize++;}getLeaveSize(root.left);getLeaveSize(root.right);return leaveSize;
}

同样的,也可以换一种子问题思路来考虑,要求当前root有多少个叶子结点,其实就是相当于求root左树的叶子结点的个数 + root右树的叶子结点的个数 

于是有如下代码:

public int getLeaveSize(TreeNode root) {if(root == null) return 0;if(root.left == null && root.right == null) {return 1;}int leftLeaveSize = getLeaveSize(root.left);int rightLeaveSize = getLeaveSize(root.right);return leftLeaveSize + rightLeaveSize;
}

下图为部分递归过程,注意先递出去,再归回来 

3. getKLevelNodeCount方法 获得第K层的结点的个数

root这棵树的第K层的结点的个数 = root.left第K - 1层的结点的个数 + root.right第K - 1层的结点的个数

如上图,若像求第3层的结点的个数,就等于求root(A).left(B)的第二层 + root(A).right(C)的第二层

于是有代码如下:

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);
}

遍历模拟图为:

4. getHeight方法 获得二叉树高度

分析:整棵树的高度 = root左树的高度 + root右树的高度 + 1

于是有如下代码:

public int getTreeHeight(TreeNode root) {if(root == null) return 0;int leftTreeHeight = getTreeHeight(root.left);int rightTreeHeight = getTreeHeight(root.right);return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
}

如下图为递归的部分过程 

5. find方法 检查二叉树是否存在值为val的元素

find方法,对比之前的数据结构查找,也是在整个数据结构中遍历一次,定义一个标识,如果有,就标识为ture,否则为false。

于是有如下代码:补充:下面代码是使用先序遍历来进行的查找

public boolean find(TreeNode root, char value) {if(root == null) return false;if(root.val == value) {return true;}boolean leftFlg = find(root.left, value);if(leftFlg == true) {return true;}boolean rightFlg = find(root.right, value) {return true;}    return false;
}

相关文章:

java数据结构_二叉树_5.5

2.7 二叉树的相关操作 1. size方法 获取二叉树元素个数 思路:遍历思路,在前面文章中,前序 中序 后序遍历的时候,会把树中的所有结点遍历一次。可以添加一个计数器,遍历一个结点就加一次。 于是有如下代码&#xff1…...

Deepseek-R1推理模型API接入调用指南 ChatGPT Web Midjourney Proxy 开源项目接入Deepseek教程

DeepSeek-R1和OpenAI o1模型都属于推理任务模型,两个模型各有优点:DeepSeek-R1 在后训练阶段大规模使用了强化学习技术,在仅有极少标注数据的情况下,极大提升了模型推理能力。在数学、代码、自然语言推理等任务上,性能…...

计算机网络(4)TCP断开

1、TCP 断开连接四次挥手流程 TCP 断开连接是通过四次挥手方式。双方都可以主动断开连接,断开连接后主机中的「资源」将被释放。 2、为什么 TIME_WAIT 等待的时间是 2MSL? 3、为什么需要 TIME_WAIT 状态? 4、拔掉网线后, 原本的 …...

科技云报到:科技普惠潮流渐起,“开源”将带我们走向何方?

科技云报到原创。 开源决定软件未来,已成为全球技术和产业创新的主导模式之一。“开源”思想的诞生,可以说是计算机发展史中极具理想主义和浪漫主义色彩的一页,是科技自由与技术极客思想的延伸。 数字化浪潮奔涌,从软件开发的底…...

【论文笔记】On Generative Agents in Recommendation

论文信息 标题: On Generative Agents in Recommendation 会议: SIGIR 24 —— CCF-A 作者: An Zhang, Yuxin Chen, Leheng Sheng 文章链接: On Generative Agents in Recommendation 代码链接: On Generative Agents…...

使用 Spring Boot 和 Canal 实现 MySQL 数据库同步

文章目录 前言一、背景二、Canal 简介三、主库数据库配置1.主库配置2.创建 Canal 用户并授予权限 四.配置 Canal Server1.Canal Server 配置文件2.启动 Canal Server 五.开发 Spring Boot 客户端1. 引入依赖2. 配置 Canal 客户端3. 实现数据同步逻辑 六.启动并测试七.注意事项八…...

vue3 在element-plus表格使用render-header

在vue2中 element表格render-header 源码是有返回h()函数的 在vue3 element-plus 表格源码 render-header函数没有返回h函数了 所以需要用render-header方法中创建虚拟DOM节点的话需要引用h方法 <el-table-column header-align"right" align"right" …...

算法——结合实例了解Minimax算法(极小化极大算法)

计算机科学中最有趣的事情之一就是编写一个人机博弈的程序。有大量的例子&#xff0c;最出名的是编写一个国际象棋的博弈机器。但不管是什么游戏&#xff0c;程序趋向于遵循一个被称为Minimax算法&#xff0c;伴随着各种各样的子算法在一块。本篇将简要介绍 minimax 算法&#…...

使用 DeepSeek 生成商城流程图

步骤 1.下载 mermaid 2.使用 DeepSeek 生成 mermaid 格式 3.复制内容到 4.保存备用。 结束。...

什么是GraphQL?

如果你在寻找漏洞利用方式,请参考下面的文章 GraphQL API 漏洞 |网络安全学院 GitHub - swisskyrepo/PayloadsAllTheThings: A list of useful payloads and bypass for Web Application Security and Pentest/CTF GraphQL 查询&#xff08;Query&#xff09; GraphQL 既不是…...

Spring Boot 的约定优于配置,你的理解是什么?

Spring Boot 的“约定优于配置”&#xff1a;开发效率的革命性提升 在软件开发中&#xff0c;开发者常常需要花费大量时间编写繁琐的配置文件&#xff0c;尤其是在传统的 Java EE 或 Spring 框架中。而 Spring Boot 通过“约定优于配置”&#xff08;Convention Over Configur…...

C#开源大型商城系统之B2B2C+O2O一体化_OctShop

一、应用背景与引言 在当今数字化商业的浪潮中&#xff0c;电子商务平台的构建成为众多企业拓展业务、提升竞争力的关键举措。C# 语言以其强大的功能、高效的性能以及良好的开发框架支持&#xff0c;在商城系统开发领域占据着重要地位。独立开源的大型 C# 商城系统&#xff0c…...

gitte远程仓库修改后,本地没有更新,本地与远程仓库不一致

问题 &#xff1a;gitte远程仓库修改后&#xff0c;本地没有更新&#xff0c;本地与远程仓库不一致 现象&#xff1a; [cxqiZwz9fjj2ssnshikw14avaZ rpc]$ git push Username for https://gitee.com: beihangya Password for https://beihangyagitee.com: To https://gitee.c…...

【对比】Pandas 和 Polars 的区别

Pandas vs Polars 对比表 特性PandasPolars开发语言Python&#xff08;Cython 实现核心部分&#xff09;Rust&#xff08;高性能系统编程语言&#xff09;性能较慢&#xff0c;尤其在大数据集上&#xff08;内存占用高&#xff0c;计算效率低&#xff09;极快&#xff0c;利用…...

el-input无法输入0.0001的小数,自动转换为0在vue3中的bug

今天遇到个bug&#xff0c;el-input中只能输入0.1或者输入0.1再加上00成为0.001&#xff0c;不能直接输入0.001&#xff0c;否则自动转换为0。需要去掉 v-model.number后面的 .number 源代码&#xff1a; <el-table-column label"实发数量" width"120"…...

Ubuntu 下 systemd 介绍

系列文章目录 Linux内核学习 Linux 知识&#xff08;1&#xff09; Linux 知识&#xff08;2&#xff09; WSL Ubuntu QEMU 虚拟机 Linux 调试视频 PCIe 与 USB 的补充知识 vscode 使用说明 树莓派 4B 指南 设备驱动畅想 Linux内核子系统 Linux 文件系统挂载 QEMU 通过网络实现…...

BERT文本分类(PyTorch和Transformers)畅用七个模型架构

&#xff08;PyTorch&#xff09;BERT文本分类&#xff1a;七种模型架构 &#x1f31f; 1. 介绍 使用BERT完成文本分类任务&#xff08;如情感分析&#xff0c;新闻文本分类等等&#xff09;对于NLPer已经是很基础的工作了&#xff01;虽说已迈入LLM时代&#xff0c;但是BERT…...

两步在 Vite 中配置 Tailwindcss

第一步&#xff1a;安装依赖 npm i -D tailwindcss tailwindcss/vite第二步&#xff1a;引入 tailwindcss 更改配置 // src/main.js import tailwindcss/index// vite.config.js import vue from vitejs/plugin-vue import tailwindcss from tailwindcss/viteexport default …...

【vmware虚拟机安装教程】

以下是在VMware Workstation Pro上安装虚拟机的详细教程&#xff1a; 准备工作 下载VMware Workstation Pro 访问VMware官网下载并安装VMware Workstation Pro&#xff08;支持Windows和Linux系统&#xff09;。安装完成后&#xff0c;确保已激活软件&#xff08;试用版或正式…...

文字转语音(三)FreeTTS实现

项目中有相关的功能&#xff0c;就简单研究了一下。 说明 FreeTTS 是一个基于 Java 的开源文本转语音&#xff08;TTS&#xff09;引擎&#xff0c;旨在将文字内容转换为自然语音输出。 FreeTTS 适合对 英文语音质量要求低、预算有限且需要离线运行 的场景&#xff0c;但若需…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...