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

求二叉树的高度(递归和非递归)

假设二叉树采用二叉链表存储结构,设计一个算法求二叉树的高度。

递归:

int getTreeHight(BiTree T){if(T==NULL){return 0;}else {int lh = getTreeHight(T->lchild);int rh = getTreeHight(T->rchild);return (lh>rh?lh:rh)+1;}}

时间复杂度O(n);空间复杂度O(n)

非递归

思想:先获得当前层的节点个数,遍历完队列中的节点就是处理完该层。这时候队列中所有节点就是下一层的。每处理一层,层数+1

int getTreeHight(BTree T){//树空 if(T==NULL){return 0;}//初始化队列 BTiree Q[MaxSize];int rear=-1,front=-1;Q[++rear]=T;//根入队 BTiree p;int last=0;//指向当前层最后一个结点 int count=0;//记录层数 while(front<rear){p=Q[++front];if(p->lchild){Q[++rear]=p->lchild;}if(p->rchild){Q[++rear]=p->rchild;}//当前层结点访问完毕,rear刚好指向下一层的最后一个结点 if(front==last){count++;last=rear;//指向下一层最后一个结点 }}return count;
}

时间复杂度O(n);空间复杂度O(n) 

相关文章:

求二叉树的高度(递归和非递归)

假设二叉树采用二叉链表存储结构&#xff0c;设计一个算法求二叉树的高度。 递归&#xff1a; int getTreeHight(BiTree T){if(TNULL){return 0;}else {int lh getTreeHight(T->lchild);int rh getTreeHight(T->rchild);return (lh>rh?lh:rh)1;}}时间复杂度O(n)&a…...

Java查找算法——(四)分块查找(完整详解,附有代码+案例)

文章目录 分块查找1.1普通分块查找 分块查找 1.1普通分块查找 分块原则&#xff1a; 块内无序&#xff0c;块间有序:前一块中的最大数据&#xff0c;小于后一块中所有的数据&#xff0c;块与块之间不能有数据重复的交集。块的数量一般等于数字个数开根号 核心思路&#xff…...

进制数知识(2)—— 浮点数在内存中的存储 和 易混淆的二进制知识总结

目录 1. 浮点数在内存中的存储 1.1 浮点数的大V表示法 1.2 浮点数的存储格式 1.3 浮点数的存入规则 1.4 浮点数的读取规则 1.5 补充&#xff1a;移码与掩码 1.6 题目解析 2. 易错的二进制知识 2.0 符号位到底会不会参与运算&#xff1f; 2.0.1 存储前的编码变化运算 …...

类似QQ聊天功能的Java程序

实现一个类似QQ聊天功能的Java程序需要考虑以下几个关键点&#xff1a; 用户界面&#xff1a;用于展示消息和输入消息。网络通信&#xff1a;用于客户端之间的信息传输。用户管理&#xff1a;用于管理用户的登录、注册和状态。消息存储&#xff1a;用于存储聊天记录。 这里提…...

Redis 键值对数据库学习

目录 一、介绍 二、安装以及连接 三、设置连接密码 四、连接报错 五、redis 操作字符串以及过期时间 六、 redis 列表操作 七、redis 集合操作 八、hash 哈希操作 九、redis 发布和订阅操作 十、RDB和AOF的两种数据持久化机制 十一、 其他机器连接redis 十二、 pyt…...

逆向推理+ChatGPT,让论文更具说服力

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 使用ChatGPT辅助“逆向推理”技巧&#xff0c;可以显著提升论文的质量和说服力。逆向推理从结论出发&#xff0c;倒推所需的证据和论点&#xff0c;确保整个论证过程逻辑严密且无漏洞。…...

「JavaScript深入」一文说明白JS的执行上下文与作用域

JavaScript深入 — 执行上下文与作用域 上下文执行上下文生命周期创建阶段执行阶段回收阶段 执行栈作用域链作用域词法作用域&#xff08;静态作用域&#xff09; 上下文 变量或函数的上下文决定了它们可以访问哪些数据&#xff0c;以及它们的行为。 每个上下文都有一个关联的…...

Qt C++设计模式->组合模式

组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;允许你将对象组合成树形结构以表示部分与整体的层次关系。组合模式使得客户端可以以统一的方式对待单个对象和组合对象&#xff0c;简化了对复杂树形结构的操作。 组合模式的应用场景 组合…...

Acwing Bellman-Ford SPFA

1. Bellman-Ford 该算法适用于有负权边的情况&#xff0c;注意&#xff1a;如果有负权环的话&#xff0c;最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路&#xff0c;但求解负权回路&#xff0c;通常用SPFA算法&#xff0c…...

我能禁止使用某协议的ip禁止访问我的资源吗

是的&#xff0c;你可以禁止使用某个协议的IP地址访问你的资源。这种操作通常涉及网络防火墙、服务器配置或应用程序设置&#xff0c;具体方法取决于你的网络环境和使用的技术。以下是一些常见的实现方法&#xff1a; 1. 使用防火墙 大多数防火墙&#xff08;硬件或软件&…...

快速理解TCP协议(二)——TCP协议中的拥塞控制机制详解

在计算机网络中&#xff0c;TCP&#xff08;传输控制协议&#xff09;是一种广泛使用的面向连接的、可靠的、基于字节流的传输层通信协议。TCP协议通过一系列复杂的机制来确保数据的可靠传输&#xff0c;其中拥塞控制是至关重要的一环。本文将深入探讨TCP协议中的拥塞控制机制&…...

Linux:debug: systemtap: ubacktrace

https://docs.huihoo.com/systemtap/sourceware.org/systemtap/SystemTap_Beginners_Guide/ustack.html 这个函数可以帮助将user level的backtrace打印出来。 stap -d /bin/ls --ldd \ -e probe process("ls").function("xmalloc") {print_usyms(ubacktra…...

使用AI进行需求分析的案例研究

生成式 AI 的潜在应用场景似乎无穷无尽。虽然这令人兴奋&#xff0c;但也可能让人不知所措。因此&#xff0c;团队在使用这项技术时需要有明确的目标&#xff1a;关键是要明确生成式 AI 在团队工作中能产生哪些实质性影响。 在软件工程中&#xff0c;一个引人注目的应用场景是…...

Python内置的re库

Python内置的re库是专门用于处理正则表达式的标准库。它提供了一系列函数和类&#xff0c;使得在Python程序中可以使用正则表达式进行字符串的搜索、替换、分割等操作。re库的使用非常广泛&#xff0c;几乎任何需要复杂文本处理的场景都可以用到它。 主要函数 1、complie函数…...

毕业设计选题:基于ssm+vue+uniapp的面向企事业单位的项目申报小程序

开发语言&#xff1a;Java框架&#xff1a;ssmuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;M…...

jQuery 简介⑤属性操作

九、属性操作 jQuery的属性操作方法一览表 $("selector").val(); // 获取第一个匹配元素的value值(一般用于表单控("selector").val("Hello"); // 设置所有匹配元素的value值为"Hello" $("selector").html();// 获取第一个…...

[Linux] Linux操作系统 进程的状态

标题&#xff1a;[Linux] Linux操作系统 进程的状态 个人主页&#xff1a;水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 一、前置概念的理解 1.并行和并发 2.时间片 3.进程间具有独立性 4.等待的本质 正文开始&#xff1a; 在校的时候&#xff0c;你一定学过《…...

深入解析Python 中的 sortedcontainers 库:高效的排序数据结构

在日常的 Python 编程中&#xff0c;列表&#xff08;list&#xff09;、集合&#xff08;set&#xff09;和字典&#xff08;dict&#xff09;是常用的数据结构。然而&#xff0c;在某些特定的场景下&#xff0c;我们需要对数据进行排序&#xff0c;并且希望在插入、删除或访问…...

什么是服务器日志,日志有什么作用?

前言 服务器日志是指服务器等电脑设备或软件的运作记录‌。这些日志记录了服务器接收客户端处理请求的过程以及服务器对这些请求的处理结果。服务器日志对于排查和解决计算机系统和网络应用中的问题至关重要&#xff0c;因为它们包含了用于调试问题的消息、服务器状态以及其他…...

Codeforces Round 971 (Div. 4)A-G1题解

Codeforces Round 971 (Div. 4) A 就是b - a #include <bits/stdc.h> #define int long longusing namespace std;void solve() {int a, b;cin >> a >> b;cout << b - a << endl; }signed main() {ios::sync_with_stdio(false);cin.tie(0);co…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...