【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

相关文章

深度解析Python中递归下降解析器的原理与实现

《深度解析Python中递归下降解析器的原理与实现》在编译器设计、配置文件处理和数据转换领域,递归下降解析器是最常用且最直观的解析技术,本文将详细介绍递归下降解析器的原理与实现,感兴趣的小伙伴可以跟随... 目录引言:解析器的核心价值一、递归下降解析器基础1.1 核心概念解析1.2 基本架构二、简单算术表达

深度解析Java @Serial 注解及常见错误案例

《深度解析Java@Serial注解及常见错误案例》Java14引入@Serial注解,用于编译时校验序列化成员,替代传统方式解决运行时错误,适用于Serializable类的方法/字段,需注意签... 目录Java @Serial 注解深度解析1. 注解本质2. 核心作用(1) 主要用途(2) 适用位置3

Debian 13升级后网络转发等功能异常怎么办? 并非错误而是管理机制变更

《Debian13升级后网络转发等功能异常怎么办?并非错误而是管理机制变更》很多朋友反馈,更新到Debian13后网络转发等功能异常,这并非BUG而是Debian13Trixie调整... 日前 Debian 13 Trixie 发布后已经有众多网友升级到新版本,只不过升级后发现某些功能存在异常,例如网络转

Java MCP 的鉴权深度解析

《JavaMCP的鉴权深度解析》文章介绍JavaMCP鉴权的实现方式,指出客户端可通过queryString、header或env传递鉴权信息,服务器端支持工具单独鉴权、过滤器集中鉴权及启动时鉴权... 目录一、MCP Client 侧(负责传递,比较简单)(1)常见的 mcpServers json 配置

Ubuntu如何升级Python版本

《Ubuntu如何升级Python版本》Ubuntu22.04Docker中,安装Python3.11后,使用update-alternatives设置为默认版本,最后用python3-V验证... 目China编程录问题描述前提环境解决方法总结问题描述Ubuntu22.04系统自带python3.10,想升级

解决升级JDK报错:module java.base does not“opens java.lang.reflect“to unnamed module问题

《解决升级JDK报错:modulejava.basedoesnot“opensjava.lang.reflect“tounnamedmodule问题》SpringBoot启动错误源于Jav... 目录问题描述原因分析解决方案总结问题描述启动sprintboot时报以下错误原因分析编程异js常是由Ja

Maven中生命周期深度解析与实战指南

《Maven中生命周期深度解析与实战指南》这篇文章主要为大家详细介绍了Maven生命周期实战指南,包含核心概念、阶段详解、SpringBoot特化场景及企业级实践建议,希望对大家有一定的帮助... 目录一、Maven 生命周期哲学二、default生命周期核心阶段详解(高频使用)三、clean生命周期核心阶

深度剖析SpringBoot日志性能提升的原因与解决

《深度剖析SpringBoot日志性能提升的原因与解决》日志记录本该是辅助工具,却为何成了性能瓶颈,SpringBoot如何用代码彻底破解日志导致的高延迟问题,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言第一章:日志性能陷阱的底层原理1.1 日志级别的“双刃剑”效应1.2 同步日志的“吞吐量杀手”

深度解析Python yfinance的核心功能和高级用法

《深度解析Pythonyfinance的核心功能和高级用法》yfinance是一个功能强大且易于使用的Python库,用于从YahooFinance获取金融数据,本教程将深入探讨yfinance的核... 目录yfinance 深度解析教程 (python)1. 简介与安装1.1 什么是 yfinance?

Linux升级或者切换python版本实现方式

《Linux升级或者切换python版本实现方式》本文介绍在Ubuntu/Debian系统升级Python至3.11或更高版本的方法,通过查看版本列表并选择新版本进行全局修改,需注意自动与手动模式的选... 目录升级系统python版本 (适用于全局修改)对于Ubuntu/Debian系统安装后,验证Pyt