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

二叉树的深度

  1. 二叉树深度的定义
    • 二叉树的深度(高度)是指从根节点到最远叶子节点的最长路径上的节点数。例如,一个只有根节点的二叉树,其深度为1;如果根节点有两个子节点,且每个子节点又分别有两个子节点,那么这个二叉树的深度为3。
  2. 计算二叉树深度的方法
    • 递归方法
      • 递归是解决二叉树问题的常用方法。对于二叉树深度的计算,其递归的思想是:二叉树的深度等于其左子树和右子树深度的最大值加1。
      • 以下是使用Python实现的代码:
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef max_depth(root):if not root:return 0left_depth = max_depth(root.left)right_depth = max_depth(root.right)return max(left_depth, right_depth)+1# 示例用法
# 创建一个简单的二叉树
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_depth(root))
  • 层序遍历方法
    • 层序遍历二叉树可以通过队列来实现。 在遍历过程中,记录遍历的层数,最后一层的层数就是二叉树的深度。
    • 以下是使用Python实现的代码:
from collections import dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef max_depth(root):if not root:return 0queue = deque([root])depth = 0while queue:level_size = len(queue)for _ in range(level_size):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)depth += 1return depth# 示例用法
# 创建一个简单的二叉树
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_depth(root))
  1. 复杂度分析

以下是使用其他编程语言(如Java、C++)来计算二叉树深度的示例:

Java实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class BinaryTreeDepth {public static int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) + 1;}public static void main(String[] args) {TreeNode root = new TreeNode(3);root.left = new TreeNode(9);root.right = new TreeNode(20);root.right.left = new TreeNode(15);root.right.right = new TreeNode(7);System.out.println(maxDepth(root));}
}

C++实现

#include <iostream>
#include <queue>using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 递归方法计算二叉树深度
int maxDepthRecursive(TreeNode* root) {if (root == nullptr) {return 0;}int leftDepth = maxDepthRecursive(root->left);int rightDepth = maxDepthRecursive(root->right);return max(leftDepth, rightDepth) + 1;
}// 层序遍历方法计算二叉树深度
int maxDepthLevelOrder(TreeNode* root) {if (root == nullptr) {return 0;}queue<TreeNode*> q;q.push(root);int depth = 0;while (!q.empty()) {int levelSize = q.size();for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}depth++;}return depth;
}int main() {TreeNode* root = new TreeNode(3);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);cout << "递归方法计算的深度: " << maxDepthRecursive(root) << endl;cout << "层序遍历方法计算的深度: " << maxDepthLevelOrder(root) << endl;return 0;
}

不同方法的应用场景

  • 递归方法
    • 代码简洁明了,逻辑清晰,非常适合处理树结构的问题,因为树本身就是递归定义的。对于简单的二叉树深度计算,递归方法很容易理解和实现。
    • 但在处理非常大的二叉树时,由于递归调用会占用栈空间,如果二叉树非常深(特别是在最坏情况下,二叉树是一条链),可能会导致栈溢出问题。
  • 层序遍历方法
    • 层序遍历方法直观地按照树的层次来处理节点,在计算深度时更加直接。不需要额外的递归调用栈空间,因此在处理非常大的二叉树时更加稳健,不会出现栈溢出的问题。
    • 缺点是代码相对复杂一些,需要使用队列来辅助实现层序遍历,理解和编写的难度稍高。

总结

计算二叉树的深度是二叉树相关算法中的一个基础问题,通过递归和层序遍历这两种常见方法都可以有效地解决。在实际应用中,可以根据二叉树的特点(如大小、结构等)以及具体的需求来选择合适的方法。

相关文章:

二叉树的深度

二叉树深度的定义&#xff1a; 二叉树的深度&#xff08;高度&#xff09;是指从根节点到最远叶子节点的最长路径上的节点数。例如&#xff0c;一个只有根节点的二叉树&#xff0c;其深度为1&#xff1b;如果根节点有两个子节点&#xff0c;且每个子节点又分别有两个子节点&…...

MySQL命令及用法(精华版)

目录 DDL&#xff08;数据定义语言&#xff09; 数据库操作 表操作 DML&#xff08;数据操作语言&#xff09; DQL&#xff08;数据查询语言&#xff09; 基本查询 条件查询 聚合函数 分组查询 排序查询 分页查询 DCL&#xff08;数据控制语言&#xff09; 用户…...

R语言学习笔记之高效数据操作

一、概要 数据操作是R语言的一大优势&#xff0c;用户可以利用基本包或者拓展包在R语言中进行复杂的数据操作&#xff0c;包括排序、更新、分组汇总等。R数据操作包&#xff1a;data.table和tidyfst两个扩展包。 data.table是当前R中处理数据最快的工具&#xff0c;可以实现快…...

将 OneLake 数据索引到 Elasticsearch - 第二部分

作者&#xff1a;来自 Elastic Gustavo Llermaly 及 Jeffrey Rengifo 本文分为两部分&#xff0c;第二部分介绍如何使用自定义连接器将 OneLake 数据索引并搜索到 Elastic 中。 在本文中&#xff0c;我们将利用第 1 部分中学到的知识来创建 OneLake 自定义 Elasticsearch 连接器…...

Linux——冯 • 诺依曼体系结构

目录 一、冯•诺依曼体系结构原理二、内存提高冯•诺依曼体系结构效率的方法三、当用QQ和朋友聊天时数据的流动过程四、关于冯诺依曼五、总结 我们常见的计算机&#xff0c;如笔记本。我们不常见的计算机&#xff0c;如服务器&#xff0c;大部分都遵守冯诺依曼体系 流程&#…...

Java进阶(一)

目录 一.Java注解 什么是注解&#xff1f; 内置注解 元注解 二.对象克隆 什么是对象克隆? 为什么用到对象克隆 三.浅克隆深克隆 一.Java注解 什么是注解&#xff1f; java中注解(Annotation)又称java标注&#xff0c;是一种特殊的注释。 可以添加在包&#xff0c;类&…...

appium自动化环境搭建

一、appium介绍 appium介绍 appium是一个开源工具、支持跨平台、用于自动化ios、安卓手机和windows桌面平台上面的原生、移动web和混合应用&#xff0c;支持多种编程语言(python&#xff0c;java&#xff0c;Ruby&#xff0c;Javascript、PHP等) 原生应用和混合应用&#xf…...

Qt 5.14.2 学习记录 —— 이십 QFile和多线程

文章目录 1、QFile1、打开2、读写3、关闭4、程序5、其它功能 2、多线程1、演示2、锁 3、条件变量和信号量 1、QFile Qt有自己的一套文件体系&#xff0c;不过Qt也可以使用C&#xff0c;C&#xff0c;Linux的文件操作。使用Qt的文件体系和Qt自己的一些类型更好配合。 管理写入读…...

積分方程與簡單的泛函分析7.希爾伯特-施密特定理

1)def函數叫作"由核生成的(有源的)" 定义: 设 是定义在区域上的核函数。 对于函数,若存在函数使得, 则称函数是“由核生成的(有源的)”。 这里的直观理解是: 函数的“来源”可以通过核函数 与另一个函数的积分运算得到。 在积分方程理论中,这种表述常…...

使用vitepress搭建自己的博客项目

一、介绍can-vitepress-blog 什么是CAN BLOG CAN BLOG是基于vitepress二开的个人博客系统&#xff0c;他能够方便使用者快速构建自己的博客文章&#xff0c;无需繁琐的配置和复杂的代码编写。 CAN BLOG以antdv为UI设计基础&#xff0c;简洁大方&#xff0c;界面友好&#xf…...

开始步入达梦中级dba

分析内存使用需要的方法之一 disql /nolog conn sysdba/sysdbaselect value from v$parameter where nameMEMORY_LEAK_CHECK; SP_SET_PARA_VALUE(0,MEMORY_LEAK_CHECK,1); select * from V$MEM_REGINFO; select * from V$MEM_HEAP;...

如何在docker中的mysql容器内执行命令与执行SQL文件

通过 docker ps -a 查询当前运行的容器&#xff0c;找到想执行命令的容器名称。 docker ps -a若想执行sql文件&#xff0c;则将sql文件放入当前文件夹下后将项目内的 SQL 文件拷贝到 mysql 容器内部的 root下。 sudo docker cp /root/enterprise.sql mysql:/root/然后进入 my…...

S4 HANA更改Tax base Amount的字段控制

本文主要介绍在S4 HANA OP中Tax base Amount的字段控制相关设置。具体请参照如下内容&#xff1a; 1. 更改Tax base Amount的字段控制 以上配置用于控制FB60/FB65/FB70/FB75/MIRO的页签“Tax”界面是否可以修改“Tax base Amount”&#xff0c; 如果勾选Change 表示可以修改T…...

Linux权限有关

文章目录 一、添加普通用户二、Xshell下命令行的知识三、 Linux和Windows操作系统四、再探指令和Linux权限五、用户相关用户切换: 今天我们学习与Linux有关的权限等内容&#xff0c;以及一些零碎知识帮助我们理解Linux的系统和Xshell的原理。 本篇是在Xshell环境下执行的。 一…...

【github 使用相关】提交pr和commit message Conventional Commits 规范 代码提交的描述该写什么?

目录 Git 提交信息格式格式描述Subject&#xff08;标题&#xff09;Body&#xff08;正文&#xff09; 规范的标签&#xff08;Tag&#xff09;示例 CG Git 提交信息格式 格式描述 一般开源项目代码库根目录都会有一个 CONTRIBUTING.md 或者其他类似名字的文档来介绍如何开始…...

Docker—搭建Harbor和阿里云私有仓库

Harbor概述 Harbor是一个开源的企业级Docker Registry管理项目&#xff0c;由VMware公司开发。‌它的主要用途是帮助用户迅速搭建一个企业级的Docker Registry服务&#xff0c;提供比Docker官方公共镜像仓库更为丰富和安全的功能&#xff0c;特别适合企业环境使用。‌12 Harb…...

Maven的下载安装配置

maven的下载安装配置 maven是什么 Maven 是一个用于 Java 平台的 自动化构建工具&#xff0c;由 Apache 组织提供。它不仅可以用作包管理&#xff0c;还支持项目的开发、打包、测试及部署等一系列行为 Maven的核心功能 项目构建生命周期管理&#xff1a;Maven定义了项目构建…...

Rust:高性能与安全并行的编程语言

引言 在现代编程世界里&#xff0c;开发者面临的最大挑战之一就是如何平衡性能与安全性。在许多情况下&#xff0c;C/C这样的系统级编程语言虽然性能强大&#xff0c;但其内存管理的复杂性导致了各种安全漏洞。为了解决这些问题&#xff0c;Rust 作为一种新的系统级编程语言进入…...

matlab的cat()函数详解(OK)

cat函数的功能是 连接数组 功能&#xff1a; 按指定的维度连接多个向量 结构&#xff1a; C cat(dim, A, B) 按dim指定的维度连接向量A和BC cat(dim, A1, A2, A3,A4, …) 按dim指定的维度连接多个向量A1, A2,A3,A4…C cat(dim, A{:}) 将包含向量的cell或结构数组联合为一…...

将个人微信中的时间改成标准的日期时间格式

list1["10:05","上午 10:07","下午 2:07","晚上 8:07","昨天 16:07","星期天 19:27","星期二 19:27","星期四 14:27","2025年1月10日 17:43"]from datetime import datetime, time…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...