Java 数据结构中二叉树前中后序遍历非递归的具体实现详解
作者:dhdhdhdhg 发布时间:2023-02-14 12:51:18
一、前序遍历
1.题目描述
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
2.输入输出示例
示例 1:
输入:root = [1,null,2,3]
输出:[1,2,3]
示例2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
3.解题思路
前序遍历:根结点—左子树—右子树
1.判断额外情况,如果树为空,直接返回
2.创建一个栈用来保存右子树
3.先将根结点入栈,避免多次判断栈为空
4.取出栈顶元素(第一次为根结点),从上往下遍历最左侧路径中的每个结点
5.在遍历时判断当前结点的右子树是否为空,非空则入栈
6.遍历结束后,此时栈顶元素为前一个结点的右子树,将栈顶元素取出,将其看作一棵树,继续重复上述操作,即形成循环。
4.代码实现
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
//创建一个栈用来保存右子树
Stack<TreeNode> s=new Stack<>();
TreeNode cur=root;
s.push(root);
//从上往下遍历最左侧路径中的每个结点,并将其右子树保存起来---栈
while(!s.empty()||cur!=null){
cur=s.pop();
while(cur!=null){
list.add(cur.val);
if(cur.right!=null){
s.push(cur.right);
}
cur=cur.left;
}
}
return list;
}
}
二、中序遍历
1.题目描述
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
2.输入输出示例
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
3.解题思路
中序遍历:左子树—根结点—右子树
1.判断额外情况,如果树为空,直接返回
2.创建一个栈用来保存结点
3.从上往下遍历最左侧路径中的每个结点,并将其保存到栈中,走到cur==null的位置
4.此时栈顶元素为最左侧路径的最后一个结点,将其加入到list并将栈顶元素移除
5.判断最后一个结点的右子树是否为空,过程和上述的过程是一样的,直接将其右子树看作一棵树,整个过程便循环起来
4.代码实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
Stack<TreeNode> s=new Stack<>();
TreeNode cur=root;
//从上往下遍历最左侧路径中的每个结点,并将其保存到栈中
while(!s.empty()||cur!=null){
while(cur!=null){
s.push(cur);
cur=cur.left;
}
cur=s.pop();
list.add(cur.val);
cur=cur.right;
}
return list;
}
}
三、后序遍历
1.题目描述
给定一个二叉树,返回它的 后序 遍历。
2.输入输出示例
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
3.解题思路
后序遍历:左子树—右子树—根结点
1.判断额外情况,如果树为空,直接返回
2.创建一个栈用来保存遍历的结点
3找出以cur为根的二叉树中最左侧的节点,并保存所经路径中的所有结点—栈
4.此时栈顶元素为最左侧路径的最后一个结点
5.先要判断最后一个结点的右子树是否为空
如果为空,直接将结点加入list,同时将栈顶元素删除
如果不为空则将右子树看作一棵树,重新进入循环判断
注意:如果按照这样,到了最后的右子树就会一直循环出不来
解决方案:
创建一个prev用来标记已经遍历过的结点,将能否编历的条件改为:top的右子树为空||top的右子树已经遍历过
4.代码实现
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
if(root==null){
return list;
}
Stack<TreeNode> s=new Stack<>();
TreeNode cur=root;
TreeNode prev=null;//用来标记刚刚遍历过的节点
while(!s.empty()||cur!=null){
//1.找出以cur为根的二叉树中最左侧的节点,并保存所经路径中的所有节点---栈
while(cur!=null){
s.push(cur);
cur=cur.left;
}
TreeNode top=s.peek();
//top能否遍历:top的右子树为空||top的右子树已经遍历过
if(top.right==null||top.right==prev){
list.add(top.val);
prev=top;
s.pop();
}else{
cur=top.right;
}
}
return list;
}
}
来源:https://blog.csdn.net/m0_51405559/article/details/121201623
猜你喜欢
- 1 线程池的优势总体来说,线程池有如下的优势:(1)降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。(2)提高响应速度。
- 如下所示:# ===============================================================
- Ribbon是Spring Cloud Netflix全家桶中负责负载均衡的组件,它是一组类库的集合。通过Ribbon,程序员能在不涉及到具
- 一. 流的常用创建方法1-1 使用Collection下的 stream() 和 parallelStream() 方 * ist<St
- 概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.循环队列循环队列 (Circular Queue) 是一
- 1、如何解决服务之间的通信问题?[1]HTTP REST方式 使用http协议进行数据传递 json格式数据[2]RPC方式 远程过程调用
- 导读 Spring Boot方式的项目开发已经逐步成为Java应用开发领域的主流框架,它不仅可以方便地创建生产级的Spring应用
- 堆排序基本介绍1、堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),
- List 是在开发中比较常用的集合,今天总结一下 Java 中初始化 List 的几种方式。1、常规方式List<String>
- 按行读取文件package test; import java.io.*; import java.util.*; public class
- 本文介绍了浅谈Java的两种多线程实现方式,分享给大家。具有如下:一、创建多线程的两种方式Java中,有两种方式可以创建多线程:1 通过继承
- JSR303 是一套 JavaBean 参数校验的标准1、pom导入依赖<dependency><groupId>o
- 1、概括在博客中,我们将讨论如何让Spring Security OAuth2实现使用JSON Web Tokens。2、Maven 配置首
- 因为某些需求,要在特定的时间执行一些任务,比如定时删除服务器存储的数据缓存,定时获取数据以及定时发送推送等等,这时就需要用到定时任务了。定时
- yield()介绍yield()的作用是让步。它能让当前线程由“运行状态”进入到“就绪状态”,从而让其它具有相同优先级的等待线程获取执行权;
- Oracle 数据库,查询增加RowBounds限制查询条数,默认是0到1000条private final static int rowL
- 1、回顾一下JDK * 的核心参数如果我们要为target类创建一个【JDK * 对象】,那么我们必须要传入如下三个核心参数加载targ
- 本文实例讲述了Java操作Mongodb数据库实现数据的增删查改功能。分享给大家供大家参考,具体如下:首先,我们在windows下安装mon
- 一、继承引言继承关系可以对不同模块的依赖版本做统一管理,因为子模块中的依赖基本都继承于父模块,父模块中指定哪个版本,子模块就继承哪个版本,可
- spring boot是个好东西,可以不用容器直接在main方法中启动,而且无需配置文件,方便快速搭建环境。可是当我们要同时启动2个spri