【LeetCode】升级打怪之路 Day 18:二叉树题型 —— 树的深度、高度、路经

本文主要是介绍【LeetCode】升级打怪之路 Day 18:二叉树题型 —— 树的深度、高度、路经,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今日题目:

  • 104. 二叉树的最大深度
  • 111. 二叉树的最小深度
  • 110. 平衡二叉树
  • 257. 二叉树的所有路径
  • 112. 路径总和

目录

    • Problem 1:树的深度
      • LC 104. 二叉树的最大深度 【easy】
      • LC 111. 二叉树的最小深度 【易错】
    • Problem 2:树的高度
      • LC 110. 平衡二叉树 【easy】
    • Problem 3:树的路径
      • LC 257. 二叉树的所有路径 【easy】
      • LC 112. 路径之和 【easy】

今天做的题目主要围绕在二叉树的题目中常见的几个概念:深度、高度、路径。

  • 求深度:设置一个全局遍历 deepth 表示递归调用过程中当前的深度,初始化为 0,对二叉树做递归遍历,每次递归进入左子树和右子树之前 deepth++,从左子树和右子树递归出来之后 deepth--
  • 求高度:空节点高度为 0,递归遍历的后序位置上,当前高度 height = max(leftHeight, rightHeight) + 1
  • 路径:也就是二叉树“根节点”到“叶子节点”的整条路径。这里可以利用一个性质:后序迭代遍历中,到达叶子节点时的 stack 就是从最上面的根节点到这个叶子节点的路径。其实,后序迭代遍历中,迭代到任何一个节点时的 stack 都是最上面的根节点到当前节点的路径。利用这个性质,我们就能很方便地找到我们想要找的路径,关键难点在于需要流畅地写出后序遍历的迭代版代码

今天整体难度不大,这几个思路也很常见,属于基础。

Problem 1:树的深度

LC 104. 二叉树的最大深度 【easy】

104. 二叉树的最大深度 | LeetCode

难度不大,但借助这个题可以看出求深度的一个思路:

树的深度

LC 111. 二叉树的最小深度 【易错】

111. 二叉树的最小深度 | LeetCode

这个题目有个易错点:需要明确好叶子节点指的是左右子树都是 null 的节点。而且这个题目要求的深度是指根节点到叶子节点的深度:

在这里插入图片描述
注意好这些易错点,代码架构与上一个题就差不多了:

树的深度 2

Problem 2:树的高度

LC 110. 平衡二叉树 【easy】

110. 平衡二叉树 | LeetCode

这个题目计算左右子树的高度并判断是否符合平衡二叉树的要求,关键就在于求高度。

按照思路来就可以,难度不大。

Problem 3:树的路径

这里主要可以利用:在后续迭代遍历中,迭代到某一个节点时,stack 中的节点序列就是根节点到这个节点的路径。按照这个思路,只要会写后续迭代遍历的代码,难度就不大了。

当然,可以利用递归的方式来获得路径,只需要在递归函数中加一个全局变量 path 来维护当前的路径即可,难度也不大。

LC 257. 二叉树的所有路径 【easy】

257. 二叉树的所有路径 | LeetCode

这个只需要使用后续迭代遍历,并在每一个叶子节点上将当前路径加入到结果集合中就可以了:

二叉树路径

LC 112. 路径之和 【easy】

112. 路径总和

与上一个题目类似,难度也不大。

这篇关于【LeetCode】升级打怪之路 Day 18:二叉树题型 —— 树的深度、高度、路经的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/801953

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

linux环境openssl、openssh升级流程

《linux环境openssl、openssh升级流程》该文章详细介绍了在Ubuntu22.04系统上升级OpenSSL和OpenSSH的方法,首先,升级OpenSSL的步骤包括下载最新版本、安装编译... 目录一.升级openssl1.官网下载最新版openssl2.安装编译环境3.下载后解压安装4.备份

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动