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

ops/2024/11/26 10:34:51/

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

非递归遍历二叉树

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

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

更多的二叉树的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/ops/136810.html

相关文章

使用 Python 的 pdfplumber 库高效解析 PDF 文件

使用 Python 的 pdfplumber 库高效解析 PDF 文件 PDF 文件是日常办公和数据处理中常见的文件格式&#xff0c;而 pdfplumber 是一个专为 PDF 文件解析设计的 Python 库&#xff0c;可以轻松提取文本、表格、图像等内容。本文将介绍 pdfplumber 的基本功能、使用方法&#xff0…

计算机网络谢希仁第七章课后题【背诵版本】

目录 【7-01】计算机网络都面临哪几种威胁?主动攻击和被动攻击的区别是什么?对于计算机网络的安全措施都有哪些? 【7-02】 试解释以下名词:(2)拒绝服务;(3)访问控制;(4)流量分析;(5)恶意程序。 【7-03】为什么说&#xff0c;计算机网络的安全不仅仅局限于保密性?试举例说…

openssl创建自签名证书

原文地址&#xff1a;自签名证书 – 无敌牛 欢迎参观我的个人博客&#xff1a;无敌牛 – 技术/著作/典籍/分享等 1 生成私钥 openssl genrsa -out server.key 2048 2 创建证书请求文件 openssl req -new -key server.key -out server.csr 3 用私钥和证书请求文件&#xf…

opencv读写文件操作

读取图像文件 OpenCV 中使用cv2.imread()函数来读取图像文件。这个函数的第一个参数是图像文件的路径&#xff0c;第二个参数是一个可选的标志&#xff0c;用于指定读取图像的方式。示例代码&#xff1a; import cv2 # 以彩色模式读取图像&#xff08;这是默认模式&#xff09…

HTML实现 扫雷游戏

前言&#xff1a; 游戏起源与发展 扫雷游戏的雏形可追溯到 1973 年的 “方块&#xff08;cube&#xff09;” 游戏&#xff0c;后经改编出现了 “rlogic” 游戏&#xff0c;玩家需为指挥中心探出安全路线避开地雷。在此基础上&#xff0c;开发者汤姆・安德森编写出了扫雷游戏的…

Python学习——猜拳小游戏

import random player int(input(“请输入&#xff1a;剪刀 0&#xff0c;石头 1&#xff0c;布2”)) computer random.randint(0,2)# print(“玩家输入的是%d&#xff0c;电脑输入的是%d” %(player,computer)) 用于测试 if (player 0) and (computer 0) or (player 1) a…

自由学习记录(23)

Lua的学习 table.concat(tb,";") 如果表里带表&#xff0c;则不能拼接&#xff0c;表里带nil也不能&#xff0c;都会报错 true和false也不可以&#xff0c;数字和字符串可以 if要和一个end配对&#xff0c;所以 if a>b then return true end end 两个end …

前端工程化18-邂逅Promise(待更新)

6、邂逅Promise 6.1、函数对象与实例对象 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>准备_函数对象与实例对象</title> </head> <body><script>/* 函数对象、实例对象…