非递归遍历二叉树(数据结构)

news/2024/11/26 9:50:34/

我的博客主页在这里插入图片描述

非递归遍历二叉树

  • 前序遍历(迭代)
  • 中序遍历(迭代)
  • 后续遍历(迭代)

二叉树的遍历方式有:前序遍历、中序遍历、后续遍历,层序遍历,而树的大部分情况下都是通过递归的方式来进行的。
首先要明白递归是函数自身调用自身,设计了很多因素记录树中遍历的入栈 记录地址等。。。因为是在栈上开辟空间,这些操作对于时间和空间的消耗会更大,且容易溢出。迭代(非递归)它是在栈堆中开辟更大的空间,不容易溢出,且不会调用函数自身,效率也会提升很多。

更多的二叉树的oj题目在我的专栏中,感谢大家的观看

数据结构中的学习难免少不了递归的学习,递归有时候也会让代码变得更加简洁,学习递归让我们对代码有更近一步的思考。

前序遍历(迭代)

每遍历一个节点打印一次元素且将其放入栈中,直到为空时,将栈顶元素移除来并打印并让其查看另一子树是否为空节点。
在这里插入图片描述

   public static void preOrderIteration(TreeNode root){if(root==null)return ;//根节点没有属性Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);System.out.print(cur.val+" ");cur=cur.left;}cur=stack.pop();//将从栈中弹出的元素给到curcur=cur.right;//cur的右边赋值给cur是否为空}}

中序遍历(迭代)

因为中序遍历是左根右,给定一个辅助栈,每次走到最后一个节点的left或者right为空时将栈中的元素给到数组,然后再去遍历栈顶右边元素是否为空。
在这里插入图片描述

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list=new LinkedList<>();Stack<TreeNode> stack=new Stack<>();while(root!=null||!stack.isEmpty()){if(root!=null){stack.push(root);root=root.left;}else{//如果为null说明该节点的左子树为空,将栈顶元素放入数组中list.add(stack.peek().val);//检查栈顶的右节点root = stack.pop().right;}}return list;}

后续遍历(迭代)

在这里插入图片描述

   public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list=new LinkedList<>();if(root==null)return list;Stack<TreeNode> stack=new Stack<>();TreeNode prev=null;//记录上一个移除栈的元素while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;}TreeNode top = stack.peek();//查看顶部元素右树是否为空//两个条件,右树为null或者此元素右树已经出过栈则直接出栈if(top.right==null||prev==top.right){TreeNode cur = stack.pop();list.add(cur.val);prev=top;//记录上一个栈顶元素}else{root=top.right;}}return list;}

http://www.ppmy.cn/news/1550025.html

相关文章

YOLO 从标注到模型训练与检测

本篇文章将带你从数据标注开始&#xff0c;经过数据集转换和划分&#xff0c;最后训练 YOLO 模型并进行检测。包括必要的代码示例&#xff0c;以及路径和文件的详细说明&#xff0c;以帮助你完成整个流程。 1. 数据标注 首先&#xff0c;我们需要对目标检测的数据进行标注。这…

lvgl学习复选框部件和进度条部件(基于正点原子)

复选框部件&#xff08;lv_checkbox&#xff09; 复选框部件常用于选择某个内容的开启和关闭&#xff0c;可以理解为自带标签的开关。 复选框部件组成部分&#xff1a; 主体(LV_PART_MAIN) 勾选框(LV PART INDICATOR) 知识点1&#xff1a;创建复选框部件 lv_obj_t *check…

lambda的作用

lambda 的定义 lambda 是 Python 中用于创建匿名函数的关键字。匿名函数是一种没有名字的函数&#xff0c;通常用来定义简单的、一次性的函数。 lambda 的语法 lambda 参数列表: 表达式 参数列表: 函数的输入&#xff0c;可以有多个&#xff0c;用逗号分隔。表达式: 函数的…

前端高能组件库 Shadcn-UI

你是不是用 element-ui 或者 ant-design &#xff0c;然后&#xff0c;开发时常常遇到需要匹配设计稿时调样式的痛苦。 Shadcn-UI 结合tailwindcss &#xff0c;即可与让你享受组件同时随意的设置样式。 支持 VUE 官方地址&#xff1a;shadcn/ui 项目地址&#xff1a;https:…

极客时间《Redis核心技术与实战》开篇词 知识点总结

Redis 主要的数据持久化方式 RDB&#xff08;Redis Database Backup file&#xff09; RDB 是 Redis 提供的一种数据快照持久化方式&#xff0c;它会在指定的时间间隔内生成数据集的时间点快照&#xff0c;并将这些快照保存到磁盘上的一个 RDB 文件中。RDB 文件是一个压缩的二…

Docker 配置 HTTP 和 HTTPS 网络代理

前言 在内网环境中&#xff0c;为了实现全局代理上网&#xff0c;Linux 系统通常通过修改 .bashrc 或 /etc/profile 等文件&#xff0c;设置 HTTP 和 HTTPS 代理。这种方式可以为大多数应用提供代理支持&#xff0c;但 Docker 并不会自动读取系统的环境变量&#xff0c;因此需…

谷粒商城-消息队列Rabbitmq

RabbitMq参考文档 在谷粒商城项目中使用消息队列主要有以下几个重要原因&#xff1a; 异步处理提高性能 场景示例&#xff1a;在订单系统中&#xff0c;当用户提交订单后&#xff0c;系统需要完成多个操作&#xff0c;如更新库存、生成订单记录、发送订单通知等。如果这些操作…

动态规划 详解

动态规划&#xff08;Dynamic Programming, DP&#xff09;详解 动态规划是一种通过分解问题为子问题并利用子问题的解来解决原问题的算法设计方法。它通常用于解决具有 重叠子问题 和 最优子结构 性质的问题。 1. 动态规划的核心思想 1.1 重叠子问题 问题可以分解为多个子问…