【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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

基于UE5和ROS2的激光雷达+深度RGBD相机小车的仿真指南(五):Blender锥桶建模

前言 本系列教程旨在使用UE5配置一个具备激光雷达+深度摄像机的仿真小车,并使用通过跨平台的方式进行ROS2和UE5仿真的通讯,达到小车自主导航的目的。本教程默认有ROS2导航及其gazebo仿真相关方面基础,Nav2相关的学习教程可以参考本人的其他博客Nav2代价地图实现和原理–Nav2源码解读之CostMap2D(上)-CSDN博客往期教程: 第一期:基于UE5和ROS2的激光雷达+深度RG

韦季李输入法_输入法和鼠标的深度融合

在数字化输入的新纪元,传统键盘输入方式正悄然进化。以往,面对实体键盘,我们常需目光游离于屏幕与键盘之间,以确认指尖下的精准位置。而屏幕键盘虽直观可见,却常因占据屏幕空间,迫使我们在操作与视野间做出妥协,频繁调整布局以兼顾输入与界面浏览。 幸而,韦季李输入法的横空出世,彻底颠覆了这一现状。它不仅对输入界面进行了革命性的重构,更巧妙地将鼠标这一传统外设融入其中,开创了一种前所未有的交互体验。 想象

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return