Java 数据结构中二叉树前中后序遍历非递归的具体实现详解
一、前序遍历
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; } }
以上就是Java 数据结构中二叉树前中后序遍历非递归的具体实现详解的详细内容,更多关于Java 数据结构的资料请关注猪先飞其它相关文章!
原文出处:https://blog.csdn.net/m0_51405559/article/details/121201623
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19