Java数据结构第十六期:走进二叉树的奇妙世界(五)



专栏:Java数据结构秘籍
个人主页:手握风云
目录
一、非递归实现遍历二叉树
1.1. 二叉树的前序遍历
1.2. 二叉树的中序遍历
1.3. 二叉树的后序遍历
一、非递归实现遍历二叉树
1.1. 二叉树的前序遍历
我们这里要使用栈来进行实现。我们反向思考一下为什么不使用队列?如下图,前序遍历肯定是先将根结点放进去,如果是队列,根结点先进先出,然后怎么去遍历右子树呢,就无法打印的顺序了。

我们定义一个引用cur,只要cur不为null,就打印值并将该元素放入栈中。当遍历到4时,左子树为空,返回结点4并弹出,再去遍历4的右结点,然后返回结点2并弹出,让cur等于结点2的右子树并遍历。只要1的左子树没有遍历完,1就不弹出。
public class Solution {public void preorderTraversal(TreeNode root){if(root == null){return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null){stack.push(cur);System.out.print(cur.val+" ");cur = cur.left;}}
}
代码写到这里就会出现问题,原因是:当遍历到结点4的时候,4的左子树为空,就无法进入while循环。然后把4弹出去,让cur=top,问题又来了,如果结点4左边要是不为空,又得放入栈中,也需要走while循环。
我们会发现当cur走到某个结点时,如果为空,但栈不为空,此时就可以巧妙地在while外面再加一层while循环。
while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}cur = stack.pop();cur = cur.right;
}
完整代码实现:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public List<Integer> preorderTraversal(TreeNode root){List<Integer> tree = new ArrayList<>();if(root == null){return tree;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {tree.add(cur.val);stack.push(cur);cur = cur.left;}cur = stack.pop();cur = cur.right;}return tree;}
}
import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> result = new ArrayList<>();Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(6);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);result = solution.preorderTraversal(root);System.out.println(result);}
}
1.2. 二叉树的中序遍历
与前序遍历的思路相同,只是打印的时机不一样。中序遍历要在弹出的元素之后直接打印。
完整代码实现:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public List<Integer> inorderTraversal(TreeNode root){List<Integer> tree = new ArrayList<>();if(root == null){return tree;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {tree.add(cur.val);stack.push(cur);cur = cur.left;}cur = stack.pop();tree.add(cur.val);cur = cur.right;}return tree;}
}
import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> result = new ArrayList<>();Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(6);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);result = solution.inorderTraversal(root);System.out.println(result);}
}
1.3. 二叉树的后序遍历
后序遍历不能按照我们上面前序与中序的方法来做。如果结点下面还有孩子结点,如果把4弹出之后,就无法获取它的右侧,所以只能获取不能弹出。当右子树为空,才能弹出,再进行打印。

public class Solution {public void postorderTraversal(TreeNode root){if(root == null){return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;while(cur != null || !stack.isEmpty()) {while(cur != null){stack.push(cur);cur = cur.left;}top = stack.peek();if(top.right == null){stack.pop();System.out.print(top.val+" ");}else{cur = top.right;}}}
}public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);solution.postorderTraversal(root);}
}
但这样写,会存在问题:当遍历到结点5的右结点7时,会陷入死循环。那我们怎么知道这个结点被打印过?我们再定义引用prev,让prev来记录被弹出的结点。
while(cur != null || !stack.isEmpty()) {while(cur != null){stack.push(cur);cur = cur.left;}top = stack.peek();if(top.right == null || top.right == prev){stack.pop();System.out.print(top.val+" ");prev = top;}else{cur = top.right;}
完整代码实现:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public List<Integer> postorderTraversal(TreeNode root){List<Integer> tree = new ArrayList<>();if(root == null){return tree;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;TreeNode prev = null;while(cur != null || !stack.isEmpty()) {while(cur != null){stack.push(cur);cur = cur.left;}top = stack.peek();if(top.right == null || top.right == prev){tree.add(top.val);stack.pop();prev = top;}else{cur = top.right;}}return tree;}
}
import java.util.ArrayList;
import java.util.List;public class Test {public static void main(String[] args) {List<Integer> tree = new ArrayList<>();Solution solution = new Solution();TreeNode root = new TreeNode(1,new TreeNode(2),new TreeNode(3));root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(6);root.left.right.right = new TreeNode(7);root.right.right = new TreeNode(8);root.right.right.left = new TreeNode(9);tree = solution.postorderTraversal(root);System.out.println(tree);}
}
相关文章:
Java数据结构第十六期:走进二叉树的奇妙世界(五)
专栏:Java数据结构秘籍 个人主页:手握风云 目录 一、非递归实现遍历二叉树 1.1. 二叉树的前序遍历 1.2. 二叉树的中序遍历 1.3. 二叉树的后序遍历 一、非递归实现遍历二叉树 1.1. 二叉树的前序遍历 我们这里要使用栈来进行实现。我们反向思考一下为…...
【开源免费】基于SpringBoot+Vue.JS疫情管理系统(JAVA毕业设计)
本文项目编号 T 227 ,文末自助获取源码 \color{red}{T227,文末自助获取源码} T227,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...
有关Java中的集合(1):List<T>和Set<T>
学习目标 核心掌握List集合了解Set集合 1.List<T> ● java.util.List。有序列表。 ● List集合元素的特点:有序表示存取有序(因为有索引)而且可以重复 ● List常用实现类: ArrayList、LinkedList、Vector等 1.1 常用方法…...
使用 Spring Boot 实现前后端分离的海康威视 SDK 视频监控
使用 Spring Boot 实现前后端分离的海康威视 SDK 视频监控系统,可以分为以下几个步骤: 1. 系统架构设计 前端:使用 Vue.js、React 或 Angular 等前端框架实现用户界面。后端:使用 Spring Boot 提供 RESTful API,负责与…...
在 Apache Tomcat 中,部署和删除项目
在 Apache Tomcat 中,部署和删除 WAR 文件是常见的操作。以下是详细步骤: 1. 删除 WAR 文件 (1) 停止应用 进入 Tomcat 的管理界面(默认地址:http://localhost:8080/manager/html)。 找到需要删除的应用,…...
宇树科技G1人形机器人:从炫技到实用,AI驱动下的进化跃迁
宇树科技的G1人形机器人近期凭借“720度回旋踢”“走梅花桩”等高难度动作频频出圈,成为人形机器人领域的现象级产品。 G1人形机器人看似炫技的表演背后,实则暗含了技术突破的深意。G1的每一次技能升级,都是对机器人运动控制、平衡算法和A…...
给定计算预算下的最佳LLM模型尺寸与预训练数据量分配
给定计算预算下的最佳LLM模型尺寸与预训练数据量分配 FesianXu 20250304 at Wechat Search Team 前言 如果给定了计算预算 C C C,如何分配LLM的模型尺寸 N N N和训练的数据量 D D D,才能使得模型的效果 L L L最好呢?笔者在此介绍一篇经典的文…...
H5DS编辑器是如何让企业快速构建动态页面
H5DS编辑器核心亮点: 1.拖拽式操作,小白友好:无需设计与代码基础!通过简单拖拽元素、调整文字和动画,即可生成交互式H5页面。内置海量模板和素材库,支持自定义设计风格,轻松适配企业品牌需求。…...
面试题汇总(一)
熙牛医疗面经 1.平衡二叉树的概念 平衡二叉树是一种二叉搜索树,他的左右两个字数的高度差绝对值不超过1,并且左右两个子树都是一颗平衡二叉树,通过左旋,右旋,左右双旋,右左双旋,来保持平衡&…...
论坛系统测试报告
目录 一、项目背景二、论坛系统测试用例思维导图三、论坛系统测试3.1界面测试3.2登陆测试3.3主页测试3.4个人中心测试 四、自动化测试脚本4.1配置驱动4.2创建浏览器类4.3功能测试4.3.1登陆测试4.3.2注册测试4.3.3主页测试4.3.4帖子编辑4.3.5运行主代码 五、BUG分析六、测试总结…...
算法比赛中处理输入和输出
在算法比赛中,不推荐使用 Scanner 和 System.out.println()。Scanner 线程安全,有大量同步操作,读取输入时每次都要解析数据类型,处理大数据量时性能开销大、效率低,易使程序超时间限制。System.out.println() 每次调用…...
llama.cpp: GGUF格式及模型量化参数介绍
GGUF格式介绍 GGUF(GPT-Generated Unified Format)是推理框架llama.cpp 中使用的一种专为大语言模型设计的二进制文件格式,旨在实现模型的快速加载和保存,同时易于读取。GGUF格式的特点: 单文件部署:模型…...
PGlite:浏览器中运行的PostgreSQL
PGlite 是一款基于 WebAssembly(WASM)构建的轻量级 PostgreSQL 数据库引擎,旨在简化开发者在浏览器、Node.js、Bun 或 Deno 环境中运行 PostgreSQL。PGlite 无需复杂的安装或配置,特别适合开发测试、本地化应用及快速原型设计。 一…...
【C++】vector(上):vector的常用接口介绍
文章目录 前言一、vector的介绍二、vector的常用接口介绍1.vector类对象的常见构造2.vector iterator 的使用3.vector类对象的容量操作3.1 size、capacity 和 empty的使用3.2 reserve的使用3.3 resize的使用 4.vector类对象的访问(包含data:返回底层数组…...
【算法】二分查找(上)
目录 一、写好二分查找的四个步骤 二、在排序数组中查找元素的第一个和最后一个位置 三、搜索插入位置 四、x的平方根 通过上篇文章【手撕二分查找】,我们知道了二分查找的【四要素】:初始值、循环条件、mid的计算方式、左右边界更新语句。 循环条件…...
【人工智能】GPT-4 vs DeepSeek-R1:谁主导了2025年的AI技术竞争?
前言 2025年,人工智能技术将迎来更加激烈的竞争。随着OpenAI的GPT-4和中国初创公司DeepSeek的DeepSeek-R1在全球范围内崭露头角,AI技术的竞争格局开始发生变化。这篇文章将详细对比这两款AI模型,从技术背景、应用领域、性能、成本效益等多个方…...
linux nginx 安装后,发现SSL模块未安装,如何处理?
?? 主页: ?? 感谢各位大佬 点赞?? 收藏 留言?? 加关注! ?? 收录于专栏:运维工程师 文章目录 前言SSL模块安装 前言 nginx 安装后,发现SSL模块未安装,如果不需要配置SSL域名,就无关紧要。但是很多时候客户后…...
蓝桥杯 - 每日打卡(类斐波那契循环数)
题目: 解题思路: 假设输入数值为number 分析题目,如果想要解决这个问题,我们需要实现两个方法,第一个检查number是否是类斐波那契,第二个是模拟1e7 - 0的过程,因为是求最大的,那么我们从1e7开始…...
深入探索C++17文件系统库:std::filesystem全面解析
前言 在C编程中,文件系统操作是许多应用程序的基础功能之一。无论是读写文件、创建目录,还是遍历文件系统,文件系统操作几乎无处不在。然而,在C17之前,标准库并没有提供一个统一、高效且易用的文件系统操作接口。开发…...
LLM | 论文精读 | GIS Copilot : 面向空间分析的自主GIS代理
论文标题:GIS Copilot: Towards an Autonomous GIS Agent for Spatial Analysis 作者:Temitope Akinboyewa,Zhenlong Li,Huan Ning,M. Naser Lessani等 来源:arXiv DOI:10.48550/arXiv.2411.…...
从RGA注意力机制到实战:行人重识别模型核心代码与论文精讲
1. RGA注意力机制原理解析 行人重识别(Person Re-identification)是计算机视觉领域的重要课题,而注意力机制在其中扮演着关键角色。RGA(Relation-aware Global Attention)机制通过建立全局关系感知模型,显…...
Blender 3MF插件终极指南:从零开始掌握3D打印文件格式
Blender 3MF插件终极指南:从零开始掌握3D打印文件格式 【免费下载链接】Blender3mfFormat Blender add-on to import/export 3MF files 项目地址: https://gitcode.com/gh_mirrors/bl/Blender3mfFormat 3MF(3D Manufacturing Format)格…...
告别软件盗版烦恼:用YT88加密狗5分钟搞定C#/Java/Python源代码加密(附完整开发包下载)
5分钟实现多语言源代码加密:YT88加密狗实战指南 独立开发者最头疼的问题之一,就是辛苦编写的代码被轻易反编译或盗用。上周我的一个朋友就遇到了这种情况——他花了三个月开发的Python数据分析工具,刚上线两周就被破解并免费传播。这种经历在…...
为什么92%的FastAPI流式AI项目在高并发下崩溃?深度解析event loop争用、response.body迭代器生命周期与uvicorn worker模型冲突
第一章:FastAPI 2.0流式AI响应的高并发失效现象全景透视当FastAPI 2.0被用于承载大语言模型(LLM)的SSE(Server-Sent Events)或分块Transfer-Encoding: chunked流式响应时,大量并发请求下常出现连接提前终止…...
编程技巧:模式切换程序框架
目录 1.模式切换程序框架 2.实现思路 3.模式切换程序框架 4.模式切换每个模式模块化流程 5.代码 Mode1.c Mode2.c Mode3.c Global.c main.c 1.模式切换程序框架 Init:进入模式前,执行一遍,用于初始化工作 Loop:执行完In…...
Fay数字人框架终极指南:30分钟打造你的AI虚拟助手
Fay数字人框架终极指南:30分钟打造你的AI虚拟助手 【免费下载链接】Fay Fay 是一个开源的数字人类框架,集成了语言模型和数字字符。它为各种应用程序提供零售、助手和代理版本,如虚拟购物指南、广播公司、助理、服务员、教师以及基于语音或文…...
5G网络规划避坑指南:PRACH时频资源配置详解与常见配置错误排查
5G网络规划避坑指南:PRACH时频资源配置详解与常见配置错误排查 在5G网络部署与优化过程中,随机接入信道(PRACH)的配置直接影响终端接入成功率与用户体验。许多网络性能问题,如高接入延迟、频繁接入失败,往往…...
SVN 启动模式详解
SVN 启动模式详解 引言 Subversion(简称SVN)是一个开源的版本控制系统,广泛用于软件项目协作开发中。SVN的启动模式是其基本操作的核心,了解并掌握不同的启动模式对于高效使用SVN至关重要。本文将详细介绍SVN的启动模式,包括基本概念、常用模式及其应用场景。 一、SVN启…...
ofa_image-caption算力适配:A10G云GPU上稳定运行的最小配置方案
ofa_image-caption算力适配:A10G云GPU上稳定运行的最小配置方案 1. 引言 如果你正在寻找一个能自动为图片生成英文描述的本地工具,并且希望它能在消费级显卡上流畅运行,那么基于OFA模型的图像描述生成工具很可能就是你的答案。这个工具最大…...
GLM-4.1V-9B-Base惊艳效果:3D渲染图材质/光影/构图中文分析
GLM-4.1V-9B-Base惊艳效果:3D渲染图材质/光影/构图中文分析 1. 视觉理解新标杆 GLM-4.1V-9B-Base作为智谱开源的视觉多模态理解模型,在3D渲染图分析领域展现出令人惊艳的能力。不同于常规的图片识别工具,这款模型能够深入理解3D渲染图中的材…...
