当前位置: 首页 > news >正文

LeetCode题94,44,145,二叉树的前中后序遍历,非递归

注意:解题都要用到栈

一、前序遍历

题目要求

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

输入:root = [1,null,2,3]
输出:[1,2,3]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:

输入:root = [1,2]
输出:[1,2]

示例 5:

输入:root = [1,null,2]
输出:[1,2]

解题思路

我们想要用非递归的方式进行前序遍历,那么我们可以用到栈

因为遍历的值要放在链表里,所以我们先存放根节点的值,同时当前节点要放进栈里,存放完后再往左边遍历

每往左边遍历一次都要把当前根节点的值放进链表里,同时当前节点也要放进栈里

直到roo.left == null,我们就要找前一个节点的右子树为不为null,因为我们已经用栈进行存储了,所以我们可以找到前一个节点,pop一下,拿到前一个节点,再判断右子树为不为空,然后一直往回走,上述步骤,直到根节点,去判断根节点的右子树,然后也是重复上面的步骤。

代码展示

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while(root != null || !stack.empty()) {while(root != null) {list.add(root.val);stack.push(root);root = root.left;}root = stack.pop();root = root.right;}return list;}

二、中序遍历

题目要求

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

解题思路

想要用非递归的思路进行中序遍历,其实步骤和前序遍历差不多

如图:

我们要先往左边找,一直找到头,同时,每遍历一个节点也要把这个节点放进栈里

直到左边节点为空,如图:

然后开始存入链表中,存入完返回上一个节点,也要存进链表中,判断该节点的右边是否为空,为空就不往右边遍历,不为空就往右边遍历,找是否又有左子树,又开始了上面的循环

,回到根节点就不说了,都是上面的这种循环。

代码展示:

public List<Integer> inorderTraversal(TreeNode root) {//非递归List<Integer> list = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();while(root != null || !stack.empty()) {while(root != null) {stack.push(root);root = root.left;}root = stack.pop();list.add(root.val);root = root.right;}return list;}  

三、后续遍历

题目要求

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 

示例 1:

输入:root = [1,null,2,3]
输出:[3,2,1]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

解题思路

后续遍历和前面的遍历都差不多,不过因为后序遍历的顺序是左右根,我们添加完左节点后,要判断有没有右节点,这时就不能直接弹出上一个根节点了,如果上一个节点有右节点,我们就要把这个根节点重新压栈,再去遍历右边的节点,等右边没有节点了,才开始把这个根节点存到链表中。

所以我们多定义一个前一个遍历的节点,判断右节点有没有遍历过,如果遍历过,我们就直接出栈这个节点,没有遍历过我们就要压栈这个节点,去遍历右边的节点。

代码展示

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode prevAccess = null;while(root != null || !stack.empty()) {while(root != null) {stack.push(root);root = root.left;}root = stack.pop();if(root.right == null || root.right == prevAccess) {list.add(root.val);prevAccess = root;root = null;}else {stack.push(root);root = root.right;}}return list;}

http://www.lryc.cn/news/228431.html

相关文章:

  • Python 框架学习 Django篇 (九) 产品发布、服务部署
  • Git 服务器上的 LFS 下载
  • Canvas和SVG:你应该选择哪一个?
  • openGauss学习笔记-122 openGauss 数据库管理-设置密态等值查询-密态支持函数/存储过程
  • BEVFormer 论文阅读
  • Centos批量删除系统重复进程
  • VUE组件的生命周期
  • 【Git系列】Github指令搜索
  • 【OpenCV】用数组给Mat图像赋值,单/双/三通道 Mat赋值
  • Doris:读取Doris数据的N种方法
  • ceph-deploy bclinux aarch64 ceph 14.2.10
  • 爬虫项目(13):使用lxml抓取相亲信息
  • mysql-数据库三大范式是什么、mysql有哪些索引类型,分别有什么作用 、 事务的特性和隔离级别
  • 微信小程序案例3-2 计算器
  • QT QSplitter
  • 银行支付凭证截图生成器在线,工商邮政农业招商建设,画板+透明标签+图片框
  • 微服务概述
  • LabVIEW中NIPackageManager功能介绍
  • 【C语言】sem_getvalue
  • Linux的shell的$# | fi | 说明
  • C //例 7.12 用选择法对数组中10个整数按由小到大排序。
  • Spring Bean循环依赖问题及解决
  • Golang源码分析 | 程序引导过程
  • 第三章:人工智能深度学习教程-基础神经网络(第四节-从头开始的具有前向和反向传播的深度神经网络 – Python)
  • 【入门Flink】- 08Flink时间语义和窗口概念
  • 【 OpenGauss源码学习 —— 列存储(CStore)(六)】
  • MUYUCMS v2.1:一款开源、轻量级的内容管理系统基于Thinkphp开发
  • SDL2 显示文字
  • c++ future 使用详解
  • 好用的C C++ 日志宏 OutputDebugStringA 写到文件或界面