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

【leetcode】树形结构习题

二叉树的前序遍历
返回结果:[‘1’, ‘2’, ‘4’, ‘5’, ‘3’, ‘6’, ‘7’]
在这里插入图片描述在这里插入图片描述在这里插入图片描述
144.二叉树的前序遍历 - 迭代算法
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,2,3]
示例 2:
输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出:[1,2,4,5,6,7,3,8,9]
示例 3:
输入:root = []
输出:[]
示例 4:
输入:root = [1]
输出:[1]
提示:
树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function preorderTraversal(root: TreeNode | null): number[] {if (!root) return []let arr = []let stack = [root]while(stack.length) {let o = stack.pop()arr.push(o.val)o.right && stack.push(o.right)o.left && stack.push(o.left)}return arr
};

二叉树的中序遍历
返回结果:[‘4’, ‘2’, ‘5’, ‘1’, ‘6’, ‘3’, ‘7’]
在这里插入图片描述在这里插入图片描述在这里插入图片描述
94.二叉树的中序遍历
给定一个二叉树的根节点 root ,返回它的中序遍历 。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function inorderTraversal(root: TreeNode | null): number[] {let arr = []let stack = []let o = rootwhile(stack.length || o) {while(o) {stack.push(o)o = o.left}let n = stack.pop()arr.push(n.val)o = n.right}return arr 
};

二叉树的后序遍历
返回结果:[‘4’, ‘5’, ‘2’, ‘6’, ‘7’, ‘3’, ‘1’]
在这里插入图片描述在这里插入图片描述在这里插入图片描述
145.二叉树的后序遍历
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
示例 1:
输入:root = [1,null,2,3]
输出:[3,2,1]
示例 2:
输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出:[4,6,7,5,2,9,8,3,1]
示例 3:
输入:root = []
输出:[]
示例 4:
输入:root = [1]
输出:[1]
提示:
树中节点的数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function postorderTraversal(root: TreeNode | null): number[] {if (!root) return []let arr = []let stack = [root]while(stack.length) {let o = stack.pop()arr.unshift(o.val)o.left && stack.push(o.left)o.right && stack.push(o.right)}return arr
};

111.二叉树的最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
树中节点数的范围在 [0, 105] 内-1000 <= Node.val <= 1000

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var minDepth = function(root) {if (!root) return 0let stack = [[root,1]]while( stack.length ) {let [o,n] = stack.shift()if (!o.left && !o.right) {return n}if (o.left) stack.push([o.left, n+1])if (o.right) stack.push([o.right, n+1])}
};

104.二叉树的最大深度
给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:3
示例 2:
输入:root = [1,null,2]
输出:2
提示:
树中节点的数量在 [0, 104] 区间内。-100 <= Node.val <= 100

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function maxDepth(root: TreeNode | null): number {if (!root) return 0let stack = [root]let num = 0while(stack.length) {let len = stack.lengthnum++while(len--) {let o = stack.shift()o.left && stack.push(o.left)o.right && stack.push(o.right)}}return num
};

226.翻转二叉树
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 1:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
示例 2:
输入:root = [2,1,3]
输出:[2,3,1]
示例 3:
输入:root = []
输出:[]
提示:
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function invertTree(root: TreeNode | null): TreeNode | null {if (root === null) return nulllet tmp = root.leftroot.left = root.rightroot.right = tmpinvertTree(root.left)invertTree(root.right)return root
};

100.相同的树
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3]
输出:true
示例 2:
输入:p = [1,2], q = [1,null,2]
输出:false
示例 3
输入:p = [1,2,1], q = [1,1,2]
输出:false
提示:
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {if (p === null && q === null) return trueif (p === null || q === null) return falseif (p.val !== q.val) return falsereturn isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

相关文章:

【leetcode】树形结构习题

二叉树的前序遍历 返回结果&#xff1a;[‘1’, ‘2’, ‘4’, ‘5’, ‘3’, ‘6’, ‘7’] 144.二叉树的前序遍历 - 迭代算法 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,…...

在ros2中安装gazebo遇到报错

安装命令&#xff1a; sudo apt-get install ros-${ROS_DISTRO}-ros-gz 报错如下&#xff1a; E: Unable to locate package ros-galactic-ros-gz 解决方法&#xff1a; 用如下安装命令&#xff1a; sudo apt install ros-galactic-ros-ign 问题解决&#xff01;...

VMware vSphere 8.0 Update 3b 发布下载,新增功能概览

VMware vSphere 8.0 Update 3b 发布下载&#xff0c;新增功能概览 vSphere 8.0U3 | ESXi 8.0U3 & vCenter Server 8.0U3 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-vsphere-8-u3/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页…...

在设计开发中,如何提高网站的用户体验?

在网站设计开发中&#xff0c;提高用户体验是至关重要的。良好的用户体验不仅能提升用户的满意度和忠诚度&#xff0c;还能增加转化率和用户留存率。以下是一些有效的方法和策略&#xff1a; 优化页面加载速度 减少HTTP请求&#xff1a;合并CSS和JavaScript文件以减少HTTP请求…...

油耳拿什么清理比较好?好用的无线可视挖耳勺推荐

油耳的朋友通常都是用棉签来掏耳。这种方式是很不安全的。因为使用棉签戳破耳道和棉絮掉落在耳道中而引起感染的新闻不在少数。在使用过程中更加建议大家可视挖耳勺来清理会更好。不仅清晰度得干净而且安全会更高。但最近这几年我发现可视挖耳勺市面上不合格产品很多&#xff0…...

永久配置清华源,告别下载龟速

为了每次使用 pip 时自动使用清华源&#xff0c;可以通过以下步骤进行配置&#xff1a; 方法一&#xff1a;通过命令行配置 你可以在命令行中运行以下命令来自动设置清华源&#xff1a; pip config set global.index-url https://pypi.tuna.tsinghua.edu.cn/simple此命令会将…...

什么是数据库回表,又该如何避免

目录 一. 回表的概念二. 回表的影响三. 解决方案1. 使用覆盖索引2. 合理选择索引列3. 避免选择不必要的列4. 分析和优化查询5. 定期更新统计信息6. 避免使用SELECT DISTINCT或GROUP BY7. 使用适当的数据库设计 数据库中的“回表”是指在查询操作中&#xff0c;当数据库需要访问…...

UE5中使用UTexture2D进行纹理绘制

在UE中有时需要在CPU阶段操作像素&#xff0c;生成纹理贴图等&#xff0c;此时可以通过UTexture2D来进行处理&#xff0c;例子如下&#xff1a; 1.CPP部分 首先创建一个蓝图函数库&#xff0c;将UTexture2D的绘制逻辑封装成单个函数&#xff1a; .h&#xff1a; #include &…...

Matlab simulink建模与仿真 第十六章(用户定义函数库)

参考视频&#xff1a;simulink1.1simulink简介_哔哩哔哩_bilibili 一、用户定义函数库中的模块概览 注&#xff1a;MATLAB版本不同&#xff0c;可能有些模块也会有差异&#xff0c;但大体上区别是不大的。 二、Fcn/Matlab Fcn模块 1、Fcn模块 双击Fcn模块&#xff0c;在对话…...

每天练打字2:今日状况——完成击键5第1遍,赛文速度74.71

今日跟打&#xff1a;604字 总跟打&#xff1a;99883字 记录天数&#xff1a;2435天 &#xff08;实际没有这么多天&#xff0c;这个是注册账号的天数&#xff09; 平均每天&#xff1a;41字 练习常用单字中500&#xff0c;击键5&#xff0c;键准100%&#xff0c;两遍。&#x…...

给新人的python笔记(一)

元组与列表 元组使用圆括号&#xff08;&#xff09;而不是[]列表的元素可以修改&#xff0c;但元组的元素不能修改 创建元组 menu1 (meat,fish,chicken) 访问元组 print(menu[1:3]) 修改元组 不支持 元组内置函数 len(tuple)&#xff1a;计算元组中元素个数&#xff1b…...

如何实现异步并发限制

如何实现异步并发限制 文章目录 如何实现异步并发限制方法1注意点 方法2题目要求实现方法注意点 之前一直没有系统的去总结异步并发限制的实现思路&#xff0c;今天就来做个总结吧 方法1 只有一个变量 pool&#xff1a;代表正在执行中的任务中的集合 function sleep(name, t…...

孙怡带你深度学习(2)--PyTorch框架认识

文章目录 PyTorch框架认识1. Tensor张量定义与特性创建方式 2. 下载数据集下载测试展现下载内容 3. 创建DataLoader&#xff08;数据加载器&#xff09;4. 选择处理器5. 神经网络模型构建模型 6. 训练数据训练集数据测试集数据 7. 提高模型学习率 总结 PyTorch框架认识 PyTorc…...

如何在Android上实现RTSP服务器

技术背景 在Android上实现RTSP服务器确实是一个不太常见的需求&#xff0c;因为Android平台主要是为客户端应用设计的。在一些内网场景下&#xff0c;我们更希望把安卓终端或开发板&#xff0c;作为一个IPC&#xff08;网络摄像机&#xff09;一样&#xff0c;对外提供个拉流的…...

代理导致的git错误

问题&#xff1a; 今天在clone时出现如下错误&#xff1a; fatal: unable to access https://github.com/NirDiamant/RAG_Techniques.git/: Failed to connect to 127.0.0.1 port 10089 after 2065 ms: Couldnt connect to server真是让人感到奇怪&#xff01;就在前天&#…...

Ready Go

本文首发在这里 温馨提示 XX年&#xff0c;指的是20XX年&#xff0c;后跟以前、以后之类&#xff0c;均包含本数链接较多&#xff0c;只是想言之有物&#xff0c;已拒绝相同外链&#xff0c;仅看关心的即可已尽量只引用自己的东西&#xff0c;16年后仓库(11/13)&#xff0c;2…...

Matlab simulink建模与仿真 第十三章(信号通路库)

参考视频&#xff1a;simulink1.1simulink简介_哔哩哔哩_bilibili 一、信号通路库中的模块概览 1、信号通路组 注&#xff1a;部分模块在第二章中有介绍&#xff0c;本章不再赘述。 2、信号存储和访问组 二、总线分配模块 Bus Assignment模块接受总线作为输入&#xff0c;并…...

Java中接口和抽象类的区别(语法层面的区别、设计理念层面的区别)

文章目录 1. 语法层面的区别1.1 成员属性1.2 成员方法1.3 关系 2. 设计理念层面的区别&#xff08;重点&#xff09;3. 举例理解抽象类和接口在设计理念层面的区别3.1 例一&#xff1a;门和警报3.2 例二&#xff1a;招聘3.3 例三&#xff1a;装修房子 4. 总结 1. 语法层面的区别…...

Leetcode面试经典150题-20.有效的括号

给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括…...

Git常用指令大全详解

Git常用指令大全详解 Git&#xff0c;作为目前最流行的分布式版本控制系统&#xff0c;其强大的功能和灵活性为开发者提供了极大的便利。无论是个人项目还是团队协作&#xff0c;Git都扮演着不可或缺的角色。本文将详细总结Git的常用指令&#xff0c;帮助大家更好地掌握这一工…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...