Java二叉树 (2)

🐵本篇文章将对二叉树的一些基础操作进行梳理和讲解


一、操作简述

int size(Node root);  // 获取树中节点的个数int getLeafNodeCount(Node root);  // 获取叶子节点的个数int getKLevelNodeCount(Node root,int k);  // 获取第K层节点的个数int getHeight(Node root);  // 获取二叉树的高度TreeNode find(Node root, int val);   // 检测值为value的元素是否存在void levelOrder(Node root);  //层序遍历boolean isCompleteTree(Node root)   // 判断一棵树是不是完全二叉树

接下来会对下面这棵树进行上述操作:

public class BinaryTree {static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}
}

二、代码实现

1.获取树中结点的个数

思路:定义一个nodeSize, 按照二叉树前序遍历的方式遍历这颗二叉树, 每遍历一个结点, nodeSize就+1

    public int nodeSize; //nodeSize不能写到方法内部,否则每次递归nodeSize都会被初始化为0,最终导致结果错误public int size(TreeNode root) {if (root == null) {return 0;}nodeSize++;size(root.left);size(root.right);return nodeSize;}

2. 获取树中叶子结点的个数

思路:叶子结点也就是没有左右孩子的结点,该方法的实现和上一个方法思路大体一致,定义一个leafNode,在遍历这颗二叉树的过程中,如果该节点没有左右孩子则leafNode + 1

    public static int leafNode;public int getLeafNodeCount(TreeNode root) { //计算叶子结点个数if (root == null) {return 0;}if (root.left == null && root.right == null) {leafNode++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafNode;}

3. 计算k层结点的个数

思路:假如要计算第3层结点的个数,k = 3,整个树的第3层也就是这个树的左子树(B)的第2层+右子树(C)的第2层,也就是B的左子树的第一层 + B的右子树的第一层 和C的左子树的第一层 + C的右子树的第一层,通过前序遍历的方式,每遍历到一层k就减1,当k == 1时就返回1

    public int getKLevelNodeCount(TreeNode root,int k) {//计算第k层结点的个数if (root == null) {return 0;}if (k == 1) {return 1;}k--;return getKLevelNodeCount(root.left, k) +getKLevelNodeCount(root.right, k);}

4. 获取树的高度

思路:整个树的高度也就是左子树的高度和右子树的高度的最大值+1,再通过递归的方式求左子树和右子树的高度

    public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.max(leftHeight, rightHeight) + 1;}

5. 检测值为val的元素的结点是否存在

思路:遍历这棵二叉树,找到值为val的结点后逐层返回,直接看代码:

    public TreeNode find(TreeNode root, char val) {if (root == null) {return null;}if (root.val == val) {return root;}TreeNode leftNode = find(root.left, val);//必须用一个变量来接收,否则上述返回的root没有意义,最终返回的还是nullif (leftNode != null) { //leftNode不为空说明找到了,将其返回return leftNode;}TreeNode rightNode = find(root.right, val);if (rightNode != null) {return rightNode;}return null; //没有找到val结点就返回null}

6. 层序遍历二叉树

思路:定义一个队列,先将这个树的根结点入队,之后通过循环如果队列不为空,则让队头结点出队,判断该结点的左和右是否为空,不为空的入队,如此循环知道队列为空,整个二叉树遍历完毕

    public void levelOrder(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur = queue.poll();System.out.print(cur.val +" ");if(cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}}

7. 判断一棵树是不是完全二叉树

以这棵树为例:

一开始和层序遍历的思路一样,定义一个队列,将树的根结点存入队列中,接下来设置一个循环,当队列不为空的情况下将队头元素出队,如果出队结点不为空则直接将其左右孩子入队(不用判断其左右孩子是否为空)如果出队结点为空则结束该循环

完成上述操作后再设置一个循环,循环条件仍然是队列不为空,每次循环都将队头元素出队然后进行判断,如果该结点不为空,则该树不是完全二叉树

根据上述操作对上面这棵树进行实操

将根结点入队,之后进入循环,将队头元素出队,A结点不为空所以将其左右孩子入队,之后再将队头元素出队,B结点不为空所以再将其左右孩子入队

再将C出队,C结点不为空,再将其左右孩子入队,再将D结点出队,D结点不为空,再将其左右孩子入队,之后再将队头元素出队,此时出队的元素为空,此循环结束

进入第二个循环,只要队列不为空,就出队队头元素然后对其进行判断,只要出队元素不为空,则其不是完全二叉树,上述队列全部为null,所以该树是完全二叉树

如果是下面这棵树,在第一次循环后,会是如下情况:

在第二个循环由于D结点不为null,所以该树不是完全二叉树

代码如下:

    public boolean isCompleteTree(TreeNode root) {if (root == null) {return false;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur = queue.poll();if (cur == null) {break;}queue.offer(cur.left);queue.offer(cur.right);}while(!queue.isEmpty()) {TreeNode cur = queue.poll();if (cur != null) {return false;}}return true;}

🙉本篇文章到此结束

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/272827.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Claude3】利用Python中完成对Bedrock上的Claude的API调用

文章目录 1. 前期准备工作2. 安装和配置AWS CLI v23. 使用AWS configure命令配置AWS凭据4. 安装访问Bedrock的SDK5. 访问Amazon Bedrock UI6. 订阅Bedrock上的Claude模型7. 通过CLI命令列出所有可用的Claude模型8. 向Claude 3 Sonnet on Bedrock生成文本9. 参考链接 1. 前期准备…

云原生架构设计:分布式消息队列技术解析

消息队列是在消息传输过程中保存消息的容器&#xff0c;消息队列管理器在将消息从源到目标时充当中间人的角色&#xff0c;消息队列的主要目的是提供路由并保证消息的可靠传递。如果发送消息时接收者不可用&#xff0c;那消息队列就会保留消息&#xff0c;直到下次成功消费为止…

Excel 快速填充/输入内容

目录 一. Ctrl D/R 向下/右填充二. 批量输入内容 一. Ctrl D/R 向下/右填充 ⏹如下图所示&#xff0c;通过快捷键向下和向右填充数据 &#x1f914;当选中第一个单元格之后&#xff0c;可以按住Shift后&#xff0c;再选中最后一个单元格&#xff0c;可以选中第一个单元格和最…

CleanMyMac X4.14.7永久免费Mac电脑清理和优化软件

CleanMyMac X 是一款功能强大的 Mac 清理和优化软件&#xff0c;适合以下几类人群使用&#xff1a; 需要定期清理和优化 Mac 的用户&#xff1a;随着时间的推移&#xff0c;Mac 设备上可能会积累大量的无用文件、缓存和垃圾&#xff0c;导致系统运行缓慢。CleanMyMac X 的智能扫…

DataLoader

import torchvision from torch.utils.data import DataLoader from torch.utils.tensorboard import SummaryWriter# 准备的测试数据集 数据放在了CIFAR10文件夹下test_data torchvision.datasets.CIFAR10("./CIFAR10",trainFalse, transformtorchvision.transfor…

React useMemo钩子指南:优化计算性能

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【解读】OWASP大语言模型应用程序十大风险

OWASP大型语言模型应用程序前十名项目旨在教育开发人员、设计师、架构师、经理和组织在部署和管理大型语言模型&#xff08;LLM&#xff09;时的潜在安全风险。该项目提供了LLM应用程序中常见的十大最关键漏洞的列表&#xff0c;强调了它们的潜在影响、易利用性和在现实应用程序…

[Spring] IoC 控制反转和DI依赖注入和Spring中的实现以及常见面试题

目录 1. 什么是Spring 2.什么是IoC容器 3.通过实例来深入了解IoC容器的作用 3.1造一量可以定义车辆轮胎尺寸的车出现的问题 3.2解决方法 3.3IoC优势 4.DI介绍 5.Spring中的IoC和DI的实现 5.1.存对象 5.1.2 类注解 5.1.3 方法注解 5.2取对像 (依赖注入) 5.2.1.属性…

如何使用Hexo搭建个人博客

文章目录 如何使用Hexo搭建个人博客环境搭建连接 Github创建 Github Pages 仓库本地安装 Hexo 博客程序安装 HexoHexo 初始化和本地预览 部署 Hexo 到 GitHub Pages开始使用发布文章网站设置更换主题常用命令 插件安装解决成功上传github但是web不更新不想上传文章处理方式链接…

复盘-word

word-大学生网络创业交流会 设置段落&#xff0c;段后行距才有分 word-选中左边几行字进行操作 按住alt键进行选中 word复制excel随excel改变&#xff08;选择性粘贴&#xff09; 页边距为普通页边距定义 ##### word 在内容控件里面填文字&#xff08;调属性&#xff09…

BC134 蛇形矩阵

一&#xff1a;题目 二&#xff1a;思路分析 2.1 蛇形矩阵含义 首先&#xff0c;这道题我们要根据这个示例&#xff0c;找到蛇形矩阵是怎么移动的 这是&#xff0c;我们可以标记一下每次移动到方向 我们根据上图可以看出&#xff0c;蛇形矩阵一共有两种方向&#xff0c;橙色…

LLM 推理优化探微 (2) :Transformer 模型 KV 缓存技术详解

编者按&#xff1a;随着 LLM 赋能越来越多需要实时决策和响应的应用场景&#xff0c;以及用户体验不佳、成本过高、资源受限等问题的出现&#xff0c;大模型高效推理已成为一个重要的研究课题。为此&#xff0c;Baihai IDP 推出 Pierre Lienhart 的系列文章&#xff0c;从多个维…

模板不存在:./Application/Home/View/OnContact/Index.html 错误位置

模板不存在:./Application/Home/View/OnContact/Index.html 错误位置FILE: /home/huimingdedhpucixmaihndged5e/wwwroot/ThinkPHP123/Library/Think/View.class.php  LINE: 110 TRACE#0 /home/huimingdedhpucixmaihndged5e/wwwroot/ThinkPHP123/Library/Think/View.class.php(…

Flutter 开发环境搭建-VS Code篇

1.准备环境 Java SDK 下载及安装Flutter SDK 安装及配置环境变量 下载地址将flutter sdk解压目录下的bin目录放到系统环境变量中 检查环境&#xff0c;在系统终端中输入&#xff1a; # 打印flutter sdk版本号 flutter --version# 检查flutter运行环境 flutter doctor第一次运…

弹性地基梁matlab有限元编程 | 双排桩支护结构 | Matlab源码 | 理论文本

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…

uniapp小程序获取位置权限(不允许拒绝)

需求 小程序上如果需要一些定位功能&#xff0c;那么我们需要提前获取定位权限。我们页面的所有功能后续都需要在用户同意的前提下进行&#xff0c;所以一旦用户点了拒绝&#xff0c;我们应该给予提示&#xff0c;并让用于修改为允许。 实现 1.打开手机GPS 经过测试发现即使…

R语言更新版本

目录 一、更新R语言 1、安装最新的R语言版本 2、移动之前安装的packages 3、将Rstudio连接到最新的R语言 二、Rstudio更新 一、更新R语言 1、安装最新的R语言版本 查看当前R语言版本&#xff1a; R.version.string 下载最新的R语言安装包&#xff1a;R: The R Project…

图神经网络实战(4)——基于Node2Vec改进嵌入质量

图神经网络实战&#xff08;4&#xff09;——基于Node2Vec改进嵌入质量 0. 前言1. Node2Vec 架构1.2 定义邻居1.2 在随机游走中引入偏向性1.3 实现有偏随机游走 2. 实现 Node2Vec小结系列链接 0. 前言 Node2Vec 是一种基于 DeepWalk 的架构&#xff0c;DeepWalk 主要由随机游…

苍穹外卖-day01

苍穹外卖-day01 目录 苍穹外卖-day01课程内容1. 软件开发整体介绍1.1 软件开发流程1.2 角色分工1.3 软件环境 2. 苍穹外卖项目介绍2.1 项目介绍2.2 产品原型2.3 技术选型 3. 开发环境搭建3.1 前端环境搭建3.2 后端环境搭建3.2.1 熟悉项目结构3.2.2 Git版本控制3.2.3 数据库环境…

Linux学习:权限

目录 1. shell命令的工作原理与存在意义1.1 shell命令解释器存在的意义1.2 shell解释器的工作原理 2. Linux操作系统&#xff1a;用户2.1 什么是用户2.2 用户的切换操作2.3 用户权限划分的意义 3. Linux中权限的种类和意义3.1 什么是权限3.2 sudo指令与短暂提权 4. 文件类型与文…