LeetCode--HOT100题(34)

目录

  • 题目描述:94. 二叉树的中序遍历(简单)
    • 题目接口
    • 解题思路1
    • 代码
    • 解题思路2
    • 代码
  • PS:

题目描述:94. 二叉树的中序遍历(简单)

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

LeetCode做题链接:LeetCode-二叉树的中序遍历

示例 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.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {}
}

解题思路1

递归实现:
在这里插入图片描述

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();dfs(res, root);return res;}private void dfs(List<Integer> res, TreeNode root) {// 递归终止条件if (root == null) {return;}// 左 根 右dfs(res, root.left);res.add(root.val);dfs(res, root.right);}}

解题思路2

迭代实现:
可以用栈来模拟上面的调用过程

  • 不断往左子树方向走,每走一次就将当前节点保存到栈中,模拟递归的调用
  • 当前节点为空,说明左边走到头了,从栈中弹出节点并保存
  • 然后转向右边节点,继续上面整个过程

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<TreeNode>();while(stack.size()>0 || root!=null) {//不断往左子树方向走,每走一次就将当前节点保存到栈中//这是模拟递归的调用if(root!=null) {stack.add(root);root = root.left;//当前节点为空,说明左边走到头了,从栈中弹出节点并保存//然后转向右边节点,继续上面整个过程} else {TreeNode tmp = stack.pop();res.add(tmp.val);root = tmp.right;}}return res;}
}

成功!
在这里插入图片描述

PS:

感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个喔~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/103429.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

爆火「视频版ControlNet」开源了!靠提示词精准换画风,全华人团队出品

“视频版ControlNet”来了&#xff01; 让蓝衣战神秒变迪士尼公举&#xff1a; 视频处理前后&#xff0c;除了画风以外&#xff0c;其他都不更改。 女孩说话的口型都保持一致。 正在插剑的姜文&#xff0c;也能“下一秒”变猩球崛起了。 这就是由全华人团队打造的最新视频处理…

性能调优篇 二、Jvm监控及诊断工具-命令行篇

目录 一、概述1、简单命令行工具 二、jps&#xff1a;查看正在运行的Java程序&#xff08;掌握&#xff09;1、是什么&#xff1f;2、测试3、基本语法 三、jstat&#xff1a;查看jvm统计信息&#xff08;掌握&#xff09;1、是什么&#xff1f;2、基本语法3、补充 四、jinfo&am…

记录Taro大坑2丢失api无法启动

现象 解决方案 看了很多。很多说要改成一致的版本号。其实没什么用。 正确方案 再新建一个模板跑起来对比config的配置&#xff0c;以及package.json发现关闭预编译即可。预编译导致api丢失

javaWeb差缺补漏(一)【针对于自身知识点掌握情况】

前端三大件部分 1、a标签的target属性iframe标签的name属性 2、textarea标签&#xff1a;表示多行文本输入。起始标签和结束标签中的内容是默认值。 rows&#xff1a;属性设置可以显示多少行。 cols&#xff1a;属性设置每行显示多少列。 3、form表单的action提交的时候&a…

使用proxman对iOS真机进行抓包

1 打开手机的safari 输入地址 http://proxy.man/ssl 2 下载证书代开设置页面&#xff0c;安装证书 设置信任证书 打开手机设置 &#xff0c;点击通用 点击关于本机、 点击证书信任设置 打开信任设置开关 4 设置手机代理 查看需要设置的代理地址 打开界面 在手机中按…

Redis过期数据的删除策略

1 介绍 Redis 是一个kv型数据库&#xff0c;我们所有的数据都是存放在内存中的&#xff0c;但是内存是有大小限制的&#xff0c;不可能无限制的增量。 想要把不需要的数据清理掉&#xff0c;一种办法是直接删除&#xff0c;这个咱们前面章节有详细说过&#xff1b;另外一种就是…

React基础入门之虚拟Dom

React官方文档&#xff1a;https://react.docschina.org/ 说明 重要提示&#xff1a;本系列文章基础篇总结自尚硅谷课程&#xff0c;且采用类式写法&#xff01;&#xff01;最新的函数式组件写法见高级篇。 本系列文档旨在帮助vue同学更快速的学习react&#xff0c;如果你很…

【SpringCloud技术专题】「Gateway网关系列」(2)微服务网关服务的Gateway功能配置指南分析

Spring Cloud Gateway简介 Spring Cloud Gateway是Spring Cloud体系的第二代网关组件&#xff0c;基于Spring 5.0的新特性WebFlux进行开发&#xff0c;底层网络通信框架使用的是Netty&#xff0c;所以其吞吐量高、性能强劲&#xff0c;未来将会取代第一代的网关组件Zuul。Spri…

【分享】小型园区组网场景

小型园区组网图 在小型园区中&#xff0c;S2700&S3700通常部署在网络的接入层&#xff0c;S5700&S6700通常部署在网络的核心&#xff0c;出口路由器一般选用AR系列路由器。 接入交换机与核心交换机通过Eth-Trunk组网保证可靠性。 每个部门业务划分到一个VLAN中&#…

Verilog语法学习——边沿检测

边沿检测 代码 module edge_detection(input sys_clk,input sys_rst_n,input signal_in,output edge_rise,output edge_down );//存储上一个时钟周期的输入信号reg signal_in_prev;always (posedge sys_clk or negedge sys_rst_n) beginif(!sys_rst_n)signal_in_pre…

【ARM】Day9 cortex-A7核I2C实验(采集温湿度)

1. 2、编写IIC协议&#xff0c;采集温湿度值 iic.h #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h" #include "led.h" /* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4* I2C1_S…

STM32 进不了main 函数

1. 我用的是STM32L151C8T6 的芯片&#xff0c;在github 上找了个别人的例程&#xff0c;拿来当模板改&#xff0c;由于他用的是HSE 外部晶振&#xff0c;我用的是内部晶振HSI&#xff0c;所以需要改系统时钟&#xff0c;改完后debug&#xff0c; 一直进不了main 函数&#xff0…

SQL地址门牌排序,字典序转为数字序

页面有一批地址数据查询&#xff0c;结果字符排序默认是字典序的&#xff0c;所以造成了门牌3号在30号之前&#xff0c;影响用户体验&#xff1b; id, road_code, road_name, address_fullname, address_name 102 10086 人民一路 北江省南海市西湖区人民一路3号 3号 103 10086…

Docker Desktop 笔记

https://blog.csdn.net/qq_39611230/article/details/108641842 https://blog.csdn.net/KgdYsg/article/details/118213499 1、修改配置 {"registry-mirrors": ["https://registry.docker-cn.com","http://hub-mirror.c.163.com","https://…

【FAQ】视频云存储/安防监控EasyCVR视频汇聚平台如何通过角色权限自行分配功能模块?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。音视频流媒体视频平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、…

C++中机器人应用程序的行为树(ROS2)

马库斯布赫霍尔茨 一、说明 以下文章为您提供了对机器人应用程序或框架中经常使用的行为树的一般直觉&#xff1a;ROS&#xff0c;Moveit和NAV2。了解行为 Tress &#xff08;BT&#xff09; 框架的原理为您提供了在游戏领域应用知识的绝佳机会。BT可以与Unity或Unreal集成。 由…

[JavaWeb]【十】web后端开发-SpringBootWeb案例(配置文件)

目录 一、参数配置化 1.1 问题分析 1.2 问题解决&#xff08;application.properties&#xff09; 1.2.1 application.properties 1.2.2 AliOSSUtils 1.2.3 启动服务-测试 二、yml配置文件 2.1 配置格式 2.1.1 新增 application.yml 2.1.2 启动服务 2.2 XML与prope…

【广州华锐互动】VR工厂消防安全演习提供了一种全新、生动的安全教育方式

在工业生产环境中&#xff0c;安全永远是首要的考虑因素。近年来&#xff0c;随着科技的发展&#xff0c;虚拟现实(VR)技术在各种领域的应用越来越广泛&#xff0c;包括教育和培训。其中&#xff0c;VR工厂消防安全演习就是一个典型的例子&#xff0c;它为员工提供了一种全新的…

[JavaWeb]【十一】web后端开发-SpringBootWeb案例(登录)

目录 一、登录功能 1.1 思路 1.2 LoginController 1.3 EmpService 1.4 EmpServiceImpl 1.5 EmpMapper 1.6 启动服务-测试 1.7 前后端联调 二、登录校验&#xff08;重点&#xff09; 2.1 问题 2.2 问题分析 2.3 登录校验​编辑 2.4 会话技术 2.4.1 会话技术 2.4.2 …

IDEA创建Spring,Maven项目没有resources文件夹

有时新建Spring或Maven项目时&#xff0c;会出现目录中main下无resources文件夹的情况&#xff0c;来一起解决一下&#xff1a; FIles|Project Structure 在Modules模块找到对应路径&#xff0c;在main下创建resources&#xff0c;右键main&#xff0c;选择新文件夹 输入文件…