当前位置: 首页 > 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…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...