力扣hot100二刷——二叉树

embedded/2025/3/18 13:31:51/

第二次刷题不在idea写代码,而是直接在leetcode网站上写,“逼”自己掌握常用的函数。

标志掌握程度解释办法
Fully 完全掌握看到题目就有思路,编程也很流利
⭐⭐Basically 基本掌握需要稍作思考,或者看到提示方法后能解答
⭐⭐⭐Slightly 稍微掌握需要看之前写过的代码才能想起怎么做多做
⭐⭐⭐⭐absolutely no 完全没有掌握需要看题解才知道怎么做
⭐⭐⭐⭐⭐有难度的高频题需要看题解才知道怎么做,而且过几天就忘了这道题怎么做了背背
36⭐⭐⭐Easy二叉树94/二叉树的中序遍历左-中-右 递归法,当节点不为空时 将节点的左子树传入传入递归函数 添加当前节点到list 将节点的右子树传入传入递归函数 迭代法,维护一个栈,当栈不为空 或 节点不为空时 先遍历左子树,遍历过程中将节点入栈 遍历到空节点后,栈顶元素出栈,再遍历右子树Deque stack = new ArrayDeque<>();
37⭐⭐⭐Easy二叉树104/二叉树的最大深度递归法,遇到空节点返回0 将节点的左子树传入传入递归函数,并将返回值 +1 将节点的右子树传入传入递归函数,并将返回值 +1 返回两者中较大者 return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
38⭐⭐⭐Easy二叉树226/反转二叉树递归法,遇到空节点直接返回 交换当前节点的左右子树 将节点的左子树传入传入递归函数 将节点的右子树传入传入递归函数
39⭐⭐⭐Easy二叉树101/对称二叉树递归法,递归函数的输入分别为左子树的节点和右子树的节点 两节点均为空,return true 一节点为空,另一节点不为空,return false 两节点均不为空,但值不同,return false 两节点均不为空,值相同,比较left.left 和 right.right,left.right 和 right.left,返回两个结果的与
40⭐⭐⭐Easy二叉树543/二叉树的直径递归法, 分别计算当前节点的左右子树的深度 更新目前深度最大值ans:左子树深度+右子树深度 和 ans 比较 返回的是左子树深度 和 右子树深度的较大者,而不是当目前深度的最大值
41★★★★Medium二叉树102/二叉树的层序遍历关键在于:找到一个可以标志某层节点的变量,要么是层数,要么是某层的节点个数 层数递归法,递归函数的输入参数:1.当前节点 2.当前层数 当前节点为空,直接返回 层数++ 如果当前ansList的长度 < 当前层数,说明是第一次遍历到该层,要创建一个itemList加入到 list 将当前节点加入到 ansList中 对应层数位置 的itemList中 将当前节点的左子树传入传入递归函数 将当前节点的右子树传入传入递归函数 队列迭代法,维护一个队列来遍历每层元素 首先将root根节点存入队列 开始遍历二叉树,队列为空则跳出循环 维护length记录该层的节点个数 如果当前length > 0,则移除队头节点,将节点值加入到 item 集合中,并移入该节点的左右子节点(如果不为空的话),并且length-- length == 0 则将item 加入list
42★★★★Easy二叉树108/将有序数组转换为二叉搜索树递归法,核心思想:不断分割数组,数组中间位置的值一定最适合作为当前的根节点 递归参数:数组、左边界、右边界 当左边界 ≤ 右边界时,求中间索引,把数组中间索引的值作为新的节点 令节点的左右子节点 分别 为下一轮递归返回的节点 返回当前节点 如果 左边界 > 右边界,直接返回空节点。
43★★★★Medium二叉树98/验证二叉搜索树递归法,验证二叉搜索树就是看这棵树的中序遍历的序列是否是严格递增的。 维护一个pre节点来保存上一个节点,用来和当前节点比较,初始设为null,当pre != null时再比较 当前节点为空时直接返回true 将节点的左子节点传入传入递归函数 比较当前节点和上个节点的大小,当前节点 ≤ 上个节点则return fasle 节点的右子节点传入传入递归函数 返回左子树和右子树验证结果的与操作
44Medium二叉树230/二叉搜索树中第k小的元素和上题的思路是一样的,二叉搜索树的中序遍历是严格递增的,中序遍历二叉树的第k个节点即为要找的答案 巧妙定义类变量,即可用一句话找到结果 if(–k == 0) ans = root.val;
45Medium二叉树199/二叉树的右视图层数递归法: 层数从0开始 右中左递归遍历二叉树,List<List> list 维护一个集合来存放每一层的值 递归结束后,统计每层的第一个元素的集合即为答案
46⭐⭐⭐Medium二叉树114/二叉树展开为链表反先序递归遍历:右 左 中 反先序递归遍历二叉树,从最后往最前依次完成链表 每次遍历,要更新nextNode,也就是下一个节点
47★★★★Medium二叉树105/从前序与中序遍历序列构造二叉树递归遍历,3个递归参数为preorder中当前头结点的索引、inorder中当前子树的左右边界索引 由前序遍历得到头节点,在inorder中搜索头节点,为了方便搜索,维护一个map来存放inorder的值和对应的索引 根据inorder中的头节点,将inorder划分为左右子树,并将左右子树的边界分别传入递归函数 要注意右子树的递归函数略微复杂: node.right = buildTree1(root + mid - left + 1, mid + 1, right);
48⭐⭐⭐Medium二叉树437/路经总和III前序遍历+前缀和 注意,sum和map中的键都应该是long型。 由根节点从上至下前序遍历并更新sum,每次遍历先检查map中是否包含sum - target并更新ans 将当前和在map中的次数更新 将当前节点的左子节点传入递归函数,将当前节点的右子节点传入递归函数 将当前遍历层的sum在map中的次数 - 1 将当前sum 减去 当前节点的值。
49★★★★Medium二叉树236/二叉树的最近公共祖先搞明白一件事情:只要碰到一个节点(不管是p还是q)就返回当前节点,不用再遍历下面的节点了 结束递归的条件:root == null || root == p || root == q 对于当前节点,如果只有一个子树返回值不为空,另一个子树返回值为空,说明另一个节点要么也在该子树下面,他们的共同祖先就是返回的节点;要么在其他节点下,不管怎么样都不用遍历剩下的节点。
50★★Hard二叉树124/二叉树的最大路径和后序遍历 递归结束条件,空节点返回0 当前节点的左子节点和右子节点分别传入递归函数,返回结果分别为左右子树的最大路径和 更新当前最大值 ans = Math.max(ans, leftMax + rightMax + root.val); 返回值:当前节点+左子树最大路径和、当前节点+右子树最大路径和、0 三者中的较大者

图片版:
在这里插入图片描述


http://www.ppmy.cn/embedded/173600.html

相关文章

高级java每日一道面试题-2025年3月04日-微服务篇[Eureka篇]-Eureka是什么?

如果有遗漏,评论区告诉我进行补充 面试官: Eureka是什么&#xff1f; 我回答: 在Java高级面试中&#xff0c;关于Eureka的讨论通常会涵盖其基本概念、组件与架构、工作原理、高级特性以及与其他服务发现工具的比较等多个方面。以下是结合提供的内容对Eureka进行的详细解析和…

Python 鼠标轨迹算法 - 防止游戏检测

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…

C++特性——智能指针

为什么需要智能指针 对于定义的局部变量&#xff0c;当作用域结束之后&#xff0c;就会自动回收&#xff0c;这没有什么问题。 当时用new delete的时候&#xff0c;就是动态分配对象的时候&#xff0c;如果new了一个变量&#xff0c;但却没有delete&#xff0c;这会造成内存泄…

每日学习Java之一万个为什么

场景启动器&#xff1a;starter 参考常见启动器 默认配置 官网默认值 依赖 见官网 / pom父依赖 注解 SpringBootApplication&#xff1a;启动自动装配&#xff0c;配合 main SpringApplication.run&#xff08;.class,args&#xff09; SpringBootTest&#xff1a;Spri…

MySQL数据库备份工具:binlog详细操作与实战指南

MySQL的binlog&#xff08;二进制日志&#xff09;是MySQL数据库中非常重要的日志文件&#xff0c;它记录了所有对数据库的修改操作&#xff08;如INSERT、UPDATE、DELETE等&#xff09;。通过 binlog&#xff0c;我们可以实现数据恢复、主从复制、数据审计等功能。因此&#x…

【多线程】单例模式

文章目录 1. 单例模式1.1 什么是单例模式1.2 为什么使用单例模式1.3 实现单例模式1.3.1 饿汉模式1.3.1 懒汉模式 1. 单例模式 1.1 什么是单例模式 单例模式是一种创建型设计模式&#xff0c;它确保一个类只有一个实例&#xff0c;并提供一个全局访问点来访问该实例。 单例 单…

vue2:el-table列中文字前面加icon图标的两种方式

1、文字前面加icon <el-table-column label="姓名" align="left" prop="nickName"><template #default="{ row }"><i v-if="row.sync" class="el-icon-lock"></i><span>{{ row.nic…

网络安全与七层架构

网络安全与七层架构 随着互联网技术的迅猛发展&#xff0c;网络安全问题日益凸显。网络安全不仅影响到个人用户的信息安全&#xff0c;更是企业及国家安全的重要组成部分。而七层架构&#xff08;OSI模型&#xff09;为网络通信提供了理论支撑&#xff0c;能够有效地帮助我们理…