力扣hot100二刷——二叉树

news/2025/3/18 13:53:04/

第二次刷题不在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/news/1580083.html

相关文章

完善 Django 框架以实现传递视频、图片给算法模块进行识别分析

要完善 Django 框架以实现传递视频、图片给算法模块进行识别分析&#xff0c;可按以下步骤进行&#xff1a; 1. 项目初始化 首先&#xff0c;确保你已经安装了 Django 和其他必要的库&#xff08;如 Pillow 用于图片处理&#xff09;。创建一个新的 Django 项目和应用&#x…

甲骨文找回二次验证的方法(超简单)

因为更换手机丢失了二次验证。 然后给客服沟通&#xff0c;获得了找到二次验证的办法&#xff0c;希望对你有用。 1、登录到账号登陆界面&#xff0c;查看地址栏当中自己的IDCE地址&#xff08;yourIDCS_Stripe_here&#xff09;部分&#xff0c;并复制。 https://idcs-yourID…

ZooKeeper的五大核心作用及其在分布式系统中的关键价值

引言 在分布式系统的复杂架构中&#xff0c;协调多个节点的一致性、可靠性和高可用性始终是技术挑战的核心。​Apache ZooKeeper作为业界广泛采用的分布式协调服务&#xff0c;凭借其简洁的树形数据模型&#xff08;ZNode&#xff09;和高效的原子广播协议&#xff08;ZAB&…

Secure and Privacy-Preserving Decentralized Federated Learning同态加密联邦学习文献阅读

Secure and Privacy-Preserving Decentralized Federated Learning for Personalized Recommendations in Consumer Electronics Using Blockchain and Homomorphic Encryption 区块链加同态联邦学习 概括 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目…

游戏引擎学习第161天

回顾并计划今天的工作 我们从头开始编写一款完整的游戏&#xff0c;完全不依赖游戏引擎和库。我们会从最基本的渲染代码开始&#xff0c;一直到高层的AI代码&#xff0c;涵盖其中的一切。 目前&#xff0c;我们正在做一些比较轻松有趣的事情&#xff0c;可以说是比较随意的内…

登录Xshell主机及Linux基本指令

✅博客主页:爆打维c-CSDN博客​​​​​​ &#x1f43e; &#x1f539;分享c、c知识及代码 &#x1f43e; &#x1f539;Gitee代码仓库 五彩斑斓黑1 (colorful-black-1) - Gitee.com 一、操作系统简介 Linux其实跟我们熟知的Window一样&#xff0c;它们都是操作系统。 &#x…

ubuntu-学习笔记-nextjs部署相关

nextjs部署 通过域名访问项目异常ubuntu经常夯住高BPS&#xff0c;高占用无法连接&#xff0c;ssh和ftpmysql不知道为什么宕掉了 是的又是我 事情的起因是这样的&#xff0c; 我和往常一样在nextjs中写前端&#xff0c;然后打包&#xff0c;本地跑没有任何问题 通过域名访问项目…

yolo模型学习笔记——1——物体检测评估指标

1.置信度 表示模型预测的边界框中存在目标物体的概率以及反应预测框和真实框的定位质量 2.阈值 (1)定义 决定一个预测框是否被视为为正类的关键参数&#xff0c;通过调整不同的阈值&#xff0c;获得不同的精度和召回率。yolo模型会为每个预测框生成一个置信度分数&#xff0c…