一篇文章教你如何用多种迭代写法实现二叉树遍历
作者:保护眼睛 发布时间:2023-12-23 04:03:29
标签:迭代,二叉树遍历
思想
利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了,所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点,对于前序遍历、我们可以先将当前的值放进结果集中,表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程,也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。
实现
public List<Integer> preorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
res.add(root.val);
stack.add(root);
root = root.left;
}
TreeNode cur = stack.pop();
root = cur.right;
}
return res;
}
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
res.add(root.val);
stack.add(root);
root = root.left;
} else {
TreeNode cur = stack.pop();
root = cur.right;
}
}
return res;
}
public List<Integer> preorderTraversal3(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
return res;
}
public List<Integer> preorderTraversal4(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
res.add(root.val);
if (root.right != null) {
queue.addFirst(root.right);
}
if (root.left != null) {
root = root.left;
while (root != null) {
res.add(root.val);
if (root.right != null) {
queue.addFirst(root.right);
}
root = root.left;
}
}
}
return res;
}
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.add(root);
root = root.left;
} else {
TreeNode cur = stack.pop();
res.add(cur.val);
root = cur.right;
}
}
return res;
}
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.add(root);
root = root.left;
}
TreeNode cur = stack.pop();
res.add(cur.val);
root = cur.right;
}
return res;
}
public List<Integer> postorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
res.add(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
Collections.reverse(res);
return res;
}
public List<Integer> postorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty()) {
while (root != null) {
res.add(root.val);
stack.push(root);
root = root.right;
}
TreeNode cur = stack.pop();
root = cur.left;
}
Collections.reverse(res);
return res;
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null)return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
while(size!=0){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!= null){
queue.offer(cur.right);
}
size --;
}
ret.add(list);
}
return ret;
}
来源:https://blog.csdn.net/qq_45859087/article/details/119141358
0
投稿
猜你喜欢
- 五丶封装(1)包的概念与创建1>概念在我们的电脑上有许多的文件,我们为了方便管理,大致给它们进行了不同的命名。然后在不同的文件夹下面再
- //哈弗曼编码的实现类public class HffmanCoding { private int c
- Java序列化JSON时long型数值,会出现精度丢失的问题。原因:java中得long能表示的范围比js中number大,也就意味着部分数
- 近期用到了一位师兄写的C++程序,总体功能良好。使用不同的数据测试,发现了一个明显的缺点:大数据量下,预处理过程耗时很长。中科院的某计算集群
- 概述背景函数式编程的理论基础是阿隆佐·丘奇(Alonzo Church)于 1930 年代提出的 &lambd
- 在使用NavigationPage导航的时候, 我们可以给里面添加一些功能按钮, 如下所示:<ContentPage.ToolbarI
- 基于SSM框架的仓库管理系统功能:系统操作权限管理。系统提供基本的登入登出功能,同时系统包含两个角色:系统超级管理员和普通管理员,超级管理员
- SpringMVC文件下载说明: 在 SpringMVC 中,通过返回 ResponseEntity的类型,可以实现文件下载的功能案例演示1
- jdk下载并配置下载jdk下图是自己资源管理器中jdk的安装路径,双击然后next就好,不需要改什么配置手里没有安装包的,下载地址在这里 :
- 分析:label标签控件是主线程创建的,不能直接从另一个线程访问.可以这样认为:不能跨线程直接访问控件;最简单的办法就是:using Sys
- WCF实例(带步骤) <xmlnamespace prefix ="o" ns ="urn:schema
- 在Spring Cloud Netflix栈中,各个微服务都是以HTTP接口的形式暴露自身服务的,因此在调用远程服务时就必须使用HTTP客户
- 让我们来看看这段代码: import java.util.BitSet;import java.util.concurrent.C
- Object(四大方法):文章干货满满,耐性看完~~何为Object?首先先来看看官方对Object的介绍:在这里附上Java官方的查阅工具
- 执行如下的jni调用:package jni;public class JNITransObject { public nativ
- Java HashSetHashSet 基于 HashMap 来实现的,是一个不允许有重复元素的集合。HashSet 允许有 null 值。
- Java在1.5开始引入了注解,目前流行的框架都在用注解,可想而知注解的强大之处。以下通过自定义注解来深入了解java注解。一、创建自定义注
- 一、spring-boot-devtools在pom中直接引入依赖<dependency> <groupId&
- 环境:Spring5.3.12.RELEASE。Spring 3引入了一个core.onvert包,提供一个通用类型转换系统。系统定义了一个
- Java中如何输出像1-2-3-4-5 这样的字符抱歉对于这个问题我甚至不能想到一个合适的标题,但是不重要 以下操作基于 jdk 1.8St