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

双非本科准备秋招(15.3)—— 力扣二叉树

        今天学了二叉树结点表示法,建树代码如下。

public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}@Overridepublic String toString() {return String.valueOf(val);}
}

        我们建一棵树,然后使用递归的方式前中后序遍历(preOrder、inOrder、postOrder),再使用非递归方式遍历(traversal)。

public class Test {public static void main(String[] args) {TreeNode root = new TreeNode(1,new TreeNode(2, new TreeNode(4, null, null), null),new TreeNode(3, new TreeNode(5, null, null), new TreeNode(6, null, null)));preOrder(root);inOrder(root);postOrder(root);traversal(root);}

建的树如下:

        递归深度遍历:

/*** 前序*/public static void preOrder(TreeNode t){if(t == null) return;System.out.println(t.val);preOrder(t.left);preOrder(t.right);}/*** 中序*/public static void inOrder(TreeNode t){if(t == null) return;inOrder(t.left);System.out.println(t.val);inOrder(t.right);}/*** 后序*/public static void postOrder(TreeNode t){if(t == null) return;postOrder(t.left);postOrder(t.right);System.out.println(t.val);}

        非递归的方式

        使用以下代码可以通用前中后序的遍历。

    /*** 一套代码通用遍历,改造后序遍历*/public static void traversal(TreeNode t){LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(t != null || !stack.isEmpty()){if(t != null){//左子树还没处理System.out.println("前序: " + t.val);stack.push(t);t = t.left;}else{TreeNode peek = stack.peek();if(peek.right == null){//右子树为空System.out.println("中序: " + peek.val);pop = stack.pop();System.out.println("后序: " + pop.val);}else if(peek.right == pop){//右子树处理完成pop = stack.pop();System.out.println("后序: " + pop.val);}else{//右子树还没处理System.out.println("中序: " + peek.val);t = peek.right;}}}}

使用以上知识解决如下题目:

1、144. 二叉树的前序遍历 

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(root != null || !stack.isEmpty()){if(root != null){list.add(root.val);stack.push(root);root = root.left;}else{TreeNode peek = stack.peek();if(peek.right == null || peek.right == pop){pop = stack.pop();}else{root = peek.right;}}}return list;}
}

2、94. 二叉树的中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(root != null || !stack.isEmpty()){if(root != null){stack.push(root);root = root.left;}else{TreeNode peek = stack.peek();if(peek.right == null){list.add(peek.val);pop = stack.pop();}else if(peek.right == pop){pop = stack.pop();}else{list.add(peek.val);root = peek.right;}}}return list;}
}

3、145. 二叉树的后序遍历

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();TreeNode pop = null;while(root != null || !stack.isEmpty()){if(root != null){stack.push(root);root = root.left;}else{TreeNode peek = stack.peek();if(peek.right == null || peek.right == pop){pop = stack.pop();list.add(peek.val);}else{root = peek.right;}}}return list;}
}

相关文章:

双非本科准备秋招(15.3)—— 力扣二叉树

今天学了二叉树结点表示法&#xff0c;建树代码如下。 public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left …...

20240203在WIN10下使用GTX1080配置stable-diffusion-webui.git不支持float16精度出错的处理

20240203在WIN10下使用GTX1080配置stable-diffusion-webui.git不支持float16精度出错的处理 2024/2/3 21:23 缘起&#xff1a;最近学习stable-diffusion-webui.git&#xff0c;在Ubuntu20.04.6下配置SD成功。 不搞精简版本&#xff1a;Miniconda了。直接上Anacoda&#xff01; …...

京东微前端框架MicroApp简介

一、MicroApp 1.1 MicroApp简介 MicroApp是由京东前端团队推出的一款微前端框架,它从组件化的思维,基于类WebComponent进行微前端的渲染,旨在降低上手难度、提升工作效率。MicroApp无关技术栈,也不和业务绑定,可以用于任何前端框架。 官网链接:https://micro-zoe.gith…...

SpringBoot 使用定时任务(SpringTask)

Spring3.0以后自带的task&#xff0c;可以将它看成一个轻量级的Quartz&#xff0c;而且使用起来比Quartz简单许多。 使用步骤&#xff1a; 1.导入坐标 在spring-boot-starter-web坐标中&#xff0c;就包含了SpringTask&#xff0c;所以一般的Web项目都包含了。 <depende…...

国标GB/T 28181详解:设备视音频文件检索消息流程

目 录 一、设备视音频文件检索 二、设备视音频文件检索的基本要求 三、命令流程 1、流程图 2、流程描述 四、协议接口 五、产品说明 六、设备视音频文件检索的作用 七、参考 在国标GBT28181中&#xff0c;定义了设备视音频文件检索消息的流程&#xff0c;主…...

openssl自签名CA根证书、服务端和客户端证书生成并模拟单向/双向证书验证

1. 生成根证书 1.1 生成CA证书私钥 openssl genrsa -aes256 -out ca.key 2048 1.2 取消密钥的密码保护 openssl rsa -in ca.key -out ca.key 1.3 生成根证书签发申请文件(csr文件) openssl req -new -sha256 -key ca.key -out ca.csr -subj "/CCN/STFJ/LXM/ONONE/OU…...

NIO Selector简介

1.Selector和Channel关系 Selector一般称为选择器&#xff0c;也叫多路复用器&#xff0c;NIO的核心组件&#xff0c;用于检查一个或多个Channel的状态是否处于可读、可写的状态。 2.可选择通道 &#xff08;1&#xff09;不是所有的channel都能被selector复用&#xff0c;…...

2023-12蓝桥杯STEMA考试 C++ 中高级试卷解析

蓝桥杯STEMA考试 C++ 中高级试卷(12月) 一、选择题 第一题 定义字符串 string a = "Hello C++",下列选项可以获取到字符 C 的是(B)。 A、a[7] B、a[6] C、a[5] D、a[4] 第二题 下列选项中数值与其它项不同的是( C)。 A、 B、 C、 D、 第三题 定义变量 int i =…...

设计模式——2_1 命令(Command)

文章目录 定义图纸一个例子&#xff1a;空调和他的遥控器只有控制面板的空调遥控器可以撤销的操作 碎碎念命令和Runnable命令和事务 定义 把请求封装成一个对象&#xff0c;从而使你可以用不同的请求对客户进行参数化&#xff0c;对请求排队或记录请求日志&#xff0c;以及支持…...

HP数组面试题

PHP数组面试题 问题&#xff1a; 如何创建一个空数组和一个带有初始值的数组&#xff1f; 答案&#xff1a; 创建空数组&#xff1a;可以使用array()函数或空数组语法[]来创建一个空数组&#xff0c;例如$arr array();或$arr [];。创建带有初始值的数组&#xff1a;可以在创建…...

机器学习5-线性回归之损失函数

在线性回归中&#xff0c;我们通常使用最小二乘法&#xff08;Ordinary Least Squares, OLS&#xff09;来求解损失函数。线性回归的目标是找到一条直线&#xff0c;使得预测值与实际值的平方差最小化。 假设有数据集 其中 是输入特征&#xff0c; 是对应的输出。 线性回归的…...

vulhub中Adminer ElasticSearch 和 ClickHouse 错误页面SSRF漏洞复现(CVE-2021-21311)

Adminer是一个PHP编写的开源数据库管理工具&#xff0c;支持MySQL、MariaDB、PostgreSQL、SQLite、MS SQL、Oracle、Elasticsearch、MongoDB等数据库。 在其4.0.0到4.7.9版本之间&#xff0c;连接 ElasticSearch 和 ClickHouse 数据库时存在一处服务端请求伪造漏洞&#xff08…...

浅谈Zookeeper及windows下详细安装步骤

1. Zookeeper介绍 1.1 分布式系统面临的问题 分布式系统是一个硬件或软件组件分布在不同的网络计算机上&#xff0c;彼此之间仅仅通过消息传递进行通信和协调的系统。 面临的问题&#xff1a;系统每个节点之间信息同步及共享 以一个小团队为例,面临的问题 通过网络进行信息…...

vite, vue3, vue-router, vuex, ES6学习日记

学习使用vitevue3的所遇问题总结&#xff08;2024年2月1日&#xff09; 组件中使用<script>标签忘记加 setup 这会导致Navbar 没有暴露出来&#xff0c;导致使用不了&#xff0c;出现以下报错 这是因为&#xff0c;如果不用setup&#xff0c;就得使用 export default…...

25考研|660/880/1000/1800全年带刷计划

作为一个参加过两次研究生考试的老学姐&#xff0c;我觉得考研数学的难度完全取决于你自己 我自己就是一个很好的例子 21年数学题目是公认的简单&#xff0c;那一年考130的很多&#xff0c;但是我那一年只考了87分。但是22年又都说是有史以来最难的一年&#xff0c;和20年的难度…...

Mybatis基础教程及使用细节

本篇主要对Mybatis基础使用进行总结&#xff0c;包括Mybatis的基础操作&#xff0c;使用注解进行增删改查的练习&#xff1b;详细介绍xml映射文件配置过程并且使用xml映射文件进行动态sql语句进行条件查询&#xff1b;为了简化java开发提高效率&#xff0c;介绍一下依赖&#x…...

10 分钟在K8s 中部署轻量级日志系统 Loki

转载至我的博客 https://www.infrastack.cn &#xff0c;公众号&#xff1a;架构成长指南 Loki 是什么&#xff1f; Loki是由Grafana Labs开源的一个水平可扩展、高可用性&#xff0c;多租户的日志聚合系统的日志聚合系统。它的设计初衷是为了解决在大规模分布式系统中&#x…...

图像处理python基础

array 读取图片 tensor 模型预测 一般过程&#xff1a;读取数据np->tensor->model->result->np->画图 shape确保图像输入输出尺寸正确 读取图片 将在GPU上运行的tensor类型转变成在CPU上运行的np类型 三类计算机视觉任务的输入&#xff1a; 分类&#xff1…...

基于WordPress开发微信小程序2:决定开发一个wordpress主题

上一篇&#xff1a;基于WordPress开发微信小程序1&#xff1a;搭建Wordpress-CSDN博客 很快发现一个问题&#xff0c;如果使用别人的主题模板&#xff0c;多多少少存在麻烦&#xff0c;所以一咬牙&#xff0c;决定自己开发一个主题模板&#xff0c;并且开源在gitee上&#xff…...

[Python] 什么是网格搜索以及scikit-learn中GridSearch类的介绍和使用案例?

什么是网格搜索&#xff1f; 网格搜索是一种参数调优的方法&#xff0c;它可以帮助找到最佳的模型参数。在网格搜索中&#xff0c;我们先指定参数的候选值范围&#xff0c;然后枚举所有可能的参数组合&#xff0c;计算每个模型的性能指标&#xff08;比如准确率、精确率等&…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

若依项目部署--传统架构--未完待续

若依项目介绍 项目源码获取 #Git工具下载 dnf -y install git #若依项目获取 git clone https://gitee.com/y_project/RuoYi-Vue.git项目背景 随着企业信息化需求的增加&#xff0c;传统开发模式存在效率低&#xff0c;重复劳动多等问题。若依项目通过整合主流技术框架&…...