当前位置: 首页 > news >正文

leetcode刷题 | 关于二叉树的题型总结3

leetcode刷题 | 关于二叉树的题型总结3

文章目录

  • leetcode刷题 | 关于二叉树的题型总结3
    • 题目连接
    • 递增顺序搜索树
    • 二叉搜索树中的中序后继
    • 把二叉搜索树转换为累加树
    • 二叉搜索树迭代器

题目连接

897. 递增顺序搜索树 - 力扣(LeetCode)

剑指 Offer II 053. 二叉搜索树中的中序后继 - 力扣(LeetCode)

538. 把二叉搜索树转换为累加树 - 力扣(LeetCode)

173. 二叉搜索树迭代器 - 力扣(LeetCode)

递增顺序搜索树

二叉树本身是有序的,可以采用左中右的遍历顺序,使用一个prev节点保存前一个结点

class Solution {TreeNode prev = new TreeNode(-1);TreeNode node = prev;public TreeNode increasingBST(TreeNode root) {dfs(root);return node.right;}public void dfs(TreeNode root){if(root == null) return ;dfs(root.left);prev.right = root;root.left = null;prev = root;dfs(root.right);}
}

二叉搜索树中的中序后继

dfs+中序遍历

class Solution {TreeNode res = null;public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {dfs(root,p);return res;}public TreeNode dfs(TreeNode root,TreeNode p){if(root == null) return null;if(root.val > p.val){res = root;return inorderSuccessor(root.left,p);}else return inorderSuccessor(root.right,p);}
}

使用二分查找到找到cur=p的节点,使用prev记录cur的root节点

然后判断cur节点是否有右子树,如果存在则返会右子树的最左边的节点

如果没有右子树那么直接返会prev,因为pre > cur = p

class Solution {   public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {TreeNode cur = root;TreeNode prev = null;while(cur != p){if(cur.val > p.val){prev = cur;cur = cur.left;}else{cur = cur.right;}}  if(cur.right != null){cur = cur.right;while(cur.left != null){cur = cur.left;}return cur;}return prev;}
}

把二叉搜索树转换为累加树

class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;convertBST(root.right);root.val += sum; //将当前节点值和大于当前节点值的和相加sum = root.val; convertBST(root.left);return root;}  
}

使用右中左逆序中序遍历的方式并使用栈来存放前一个节点

当cur=null时遍历到了叶子节点,dep.poll() 得到该节点的父节点,将cur = 该父节点

更新cur父节点的val值,题目要求值等于原树中大于或等于 node.val 的值之和,使用sum来保存和

因为使用右中左的遍历顺序,sum始终都是累加

class Solution {public TreeNode convertBST(TreeNode root) {int sum = 0;Deque<TreeNode> deq = new ArrayDeque();      TreeNode cur = root;while(!deq.isEmpty() || cur != null){if(cur != null){deq.push(cur);cur = cur.right;}else{cur = deq.poll();sum += cur.val;cur.val = sum;cur = cur.left;}}return root;}
}

二叉搜索树迭代器

先获得中序遍历结果,然后遍历

class BSTIterator {List<TreeNode> list = null;int index;int siez;public BSTIterator(TreeNode root) {list = new ArrayList<>();index = -1;dfs(root);this.siez = list.size();}public int next() {return list.get(++index).val;}public boolean hasNext() {if (index >= siez-1) return false;return true;}public void dfs(TreeNode root){if (root == null) return ;dfs(root.left);list.add(root);dfs(root.right);}
}

使用栈存入全部的左子节点和根节点

class BSTIterator {Deque<TreeNode> deq = new ArrayDeque<>();public BSTIterator(TreeNode root) {TreeNode node  = root;while (node != null){deq.push(node);node = node.left;}}public int next() {TreeNode cur = deq.poll();if(cur.right != null){TreeNode node = cur.right;while(node != null){deq.push(node);node = node.left;//把所有的左节点都放入deq}}return cur.val;}public boolean hasNext() {return !deq.isEmpty();}
}

相关文章:

leetcode刷题 | 关于二叉树的题型总结3

leetcode刷题 | 关于二叉树的题型总结3 文章目录leetcode刷题 | 关于二叉树的题型总结3题目连接递增顺序搜索树二叉搜索树中的中序后继把二叉搜索树转换为累加树二叉搜索树迭代器题目连接 897. 递增顺序搜索树 - 力扣&#xff08;LeetCode&#xff09; 剑指 Offer II 053. 二…...

设计模式-结构型

设计模式-结构型 结构型设计模式包含&#xff1a;代理模式、适配器模式、桥接模式、装饰模式、外观设计模式、享元模式、组合模式 代理模式 核心是在具体的功能类与使用者之间建立一个中介类作为代理&#xff0c;使用者通过代理对象对真实的功能类进行访问。 在iOS开发中&am…...

【新】华为OD机试 - 预订酒店(Python)| 运气好 会考到原题

预订酒店 题目 放暑假了,小明决定到某旅游景点游玩,他在网上搜索到了各种价位的酒店(长度为 n 的数组 A),他的心理价位是 x 元,请帮他筛选出 k 个最接近 x 元的酒店(n>=k>0),并由低到高打印酒店的价格。 输入 第一行:n, k, x 第二行:A[0] A[1] A[2]...A[n-…...

【编程基础之Python】4、安装Python开发工具

【编程基础之Python】4、安装Python开发工具安装Python开发工具为什么需要开发工具Anaconda自带的开发工具PyCharm安装PyCharm运行PyCharm并创建项目总结安装Python开发工具 为什么需要开发工具 通常情况下&#xff0c;为了提高开发效率&#xff0c;需要使用相应的开发工具&a…...

5. 最长回文子串

文章目录题目描述暴力法中心扩散法参考文献题目描述 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同&#xff0c;则该字符串称为回文字符串。 示例 1&#xff1a; 输入&#xff1a;s “babad” 输出&#xff1a;“bab” 解释&a…...

内网渗透(二十四)之Windows协议认证和密码抓取-Mimikatz读取sam和lsass获取密码

系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…...

【THREE.JS】网页中的炫酷3D

web3d一、前言粒子特效二维漫画可视化后期处理二、项目使用流程2.1 项目结构2.2 基本使用2.3 项目模板2.4 技术栈三、基础动画3.1 THREE.Clock3.2 GASP四、照相机8.1 正交相机8.2 透视相机4.3 相机控制器五、画布和全屏六、几何体七、Debug UI八、纹理贴图8.1 mipmapping8.2 放…...

Go语言之 下载安装go以及vscode配置go环境

上篇请移步到Go语言之 下载安装及第一个代码_水w的博客-CSDN博客 目录 一、下载安装以及配置go环境 1 下载安装go 2 配置go环境 二、安装配置git 一、在vscode上开发golang 1 配置 2 编写代码 解决报错&#xff1a;go: go.mod file not found in current directory or …...

RBAC权限 API声明四种kubernetes对象

RBAC API声明了四种kubernetes对象: Role ClusterRole RoleBinding ClusterRoleBinding Role: 名称空间内创建授权角色&#xff0c;指定空间名字 ClusterRole: 全局角色&#xff0c;集群范围&#xff0c;对所有名称空间有效 RoleBinding: 名称…...

CDGP仿真选择题4

CDGP仿真选择题13、指标(Metrics)可以用来衡量数据管理的效果。请从下列选项中选择正确的表述: (知识点: CDGP仿真题)A.指标是衡量或评估绩效、进度、质量、效率或其他影响的标准B.这些指标用于定义每个知识领域内完成工作的可量化事实C.指标也可以测量更抽象的特性&#xff0c…...

典型相关分析与R语言实现

典型相关分析学习目标学习内容典型相关分析的原理典型相关分析的理论内容例子具体实现方法内容小结注意解决方法学习目标 我们所采用的学习内容来自B站的Lizongzhang老师的R语言的学习分享 今天学习的主要内容是关于 典型相关分析 学习内容 首先声明,典型相关分析的内容理解…...

【蓝桥集训】第一天——前缀和

作者&#xff1a;指针不指南吗 专栏&#xff1a;Acwing 蓝桥集训每日一题 &#x1f43e;输出的时候&#xff0c;注意数据类型&#x1f43e; 文章目录1.截断数组2.前缀和3.子矩阵的和4.k倍区间1.截断数组 给定一个长度为 n 的数组 a1a_1a1​,a2a_2a2​,…,ana_nan​。 现在&…...

2022-03-19青少年软件编程(C语言)等级考试试卷(六级)解析

青少年软件编程(C语言)等级考试试卷(六级) 一、编程题(共4题,共100分)T1.多项式相加 我们经常遇到两多项式相加的情况,在这里,我们就需要用程序来模拟实现把两个多项式相加到一起。首先,我们会有两个多项式,每个多项式是独立的一行,每个多项式由系数、幂数这样的多个…...

[JavaScript 刷题] 特殊数组的特征值, leetcode 1608

[JavaScript 刷题] 特殊数组的特征值, leetcode 1608 这道题在一个列表上看到的&#xff0c;刚开始用暴力解想过了就过了&#xff0c;不过后面看了一下关键字&#xff0c;发现解法……非常有趣。 时间复杂度可以从 O(n2)O(n^2)O(n2) 降为 O(nlog(n))O(n log(n))O(nlog(n))&am…...

各种素材网站大全【全部倾倒,福利倒计时-JS,HTML,游戏素材,UI,图片素材等

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 秩沅 原创 收录于专栏&#xff1a;解忧杂货铺 ⭐各种素材网站大全⭐ 文章目录⭐各种素材网站大全⭐&#x1f3b6;大家必逛的四大天王…...

影片自由,丝滑流畅,Docker容器基于WebDav协议通过Alist挂载(百度网盘/阿里云盘)Python3.10接入

使用过NAS(Network Attached Storage)的朋友都知道&#xff0c;它可以通过局域网将本地硬盘转换为局域网内的“网盘”&#xff0c;简单理解就是搭建自己的“私有云”&#xff0c;但是硬件和网络成本都太高了&#xff0c;有点可望而不可及的意思。Alist开源库则可以满足我们&…...

【新】华为OD机试 - 数组的中心位置(Python)| 运气好,这就是原题

数组的中心位置 题目 给你一个整数数组nums,请计算数组的中心位置。 数组中心位置是数组的一个下标,其左侧所有元素相乘的积等于右侧所有元素相乘的积。 数组第一个元素的左侧积为1,最后一个元素的右侧积为1。 如果数组有多个中心位置,应该返回最靠近左边的那一个。 如果数…...

小米电视安装 Plex 打造家庭影院

背景 最近突然想重温教父&#xff0c;本来想着直接投屏就可以&#xff0c;后来看了别人搭建的基于 NAS 的家庭影院很动心&#xff0c;也想依葫芦画瓢做一个&#xff0c;跟对象申请经费的时候被拒了&#xff0c;理由是有这钱还不如开个会员直接看。 我寻思不同电影在不同的平台…...

Elasticsearch:Combined fields 查询

有时一个匹配项可以覆盖多个文本字段。 在这种情况下&#xff0c;你可以使用 combined_fields 查询来搜索多个文本字段&#xff0c;就好像它们的值实际上已被索引到一个组合字段中一样。 除此之外&#xff0c;combined_fields 的主要好处是强大且易于理解的评分算法。这种做法也…...

uart 子系统

串口硬件储备知识&#xff1a; uart 在Linux 应用层的体现及使用 uart 就是串口&#xff0c;它也是属于字符设备中的一种&#xff0c;众所周知 字符设备都会在/dev/ 目录下创建节点&#xff0c;串口所创建的节点名都是以tty* 为开头&#xff0c;例如下面这些节点&#xff1a…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...

java 局域网 rtsp 取流 WebSocket 推送到前端显示 低延迟

众所周知 摄像头取流推流显示前端延迟大 传统方法是服务器取摄像头的rtsp流 然后客户端连服务器 中转多了&#xff0c;延迟一定不小。 假设相机没有专网 公网 1相机自带推流 直接推送到云服务器 然后客户端拉去 2相机只有rtsp &#xff0c;边缘服务器拉流推送到云服务器 …...