Morris Traversal-常量空间下遍历二叉树

2024-06-20 05:58

本文主要是介绍Morris Traversal-常量空间下遍历二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

通常遍历二叉树有前序(preorder)、中序(inorder)、后序(postorder)遍历有两个常用的方法:一是递归(recursive),二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度(递归本身占用stack空间或者用户自定义的stack)。递归的方法很简单,栈使用的方法见楼主另一篇文章,栈和队列在遍历二叉树中的使用。文章总结了常见的几种思路给大家参考。但这些方法都在空间复杂度为O(n),这里还有另一种经典算法,可以做到常数空间使用下遍历,并且时间复杂度仍是线性。就是Morris Traversal。
二叉树遍历最重要的问题就是如何访问完子节点后再回到母结点,否则没法访问其他的子节点。这个问题也叫回溯。之前我们使用栈来存储节点,按照适当的顺序弹出就行,现在使用常量空间,Morris的方法是利用叶子节点的空指针指向相关的母结点,从而完成回溯。下面按照三种遍历分别给出源码及过程。

一、中序遍历

步骤:
1. 如果当前结点的左孩子为空,输出当前节点,并将右孩子作为当前节点;
2. 如果当前节点的左孩子不为空,在当前节点的左子树中寻找当前节点在中序遍历下的前驱节点:
(1)如果前驱节点的右孩子为空,那么将当前节点设为该节点的右孩子,当前节点的左孩子作为新的当前节点。
(2)如果前驱节点的右孩子为当前节点,那么证明已经访问过左子树,输出当前节点,然后当前节点为自己的右孩子。
3. 重复1.2,直至当前节点为空。

morris inorder

void inorderMorrisTraversal(TreeNode *root) {TreeNode *cur = root, *prev = NULL;while (cur != NULL){if (cur->left == NULL)          // 1.{printf("%d ", cur->val);cur = cur->right;}else{// find predecessorprev = cur->left;while (prev

这篇关于Morris Traversal-常量空间下遍历二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1077291

相关文章

MySQL之InnoDB存储页的独立表空间解读

《MySQL之InnoDB存储页的独立表空间解读》:本文主要介绍MySQL之InnoDB存储页的独立表空间,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、独立表空间【1】表空间大小【2】区【3】组【4】段【5】区的类型【6】XDES Entry区结构【

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中,我们经常需要让某个元素占据容器的剩余空间,本文将介绍5种不同的方法来实现这个需求,并分析各种方法的优缺点,感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中,我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL启动报错:InnoDB表空间丢失问题及解决方法

《MySQL启动报错:InnoDB表空间丢失问题及解决方法》在启动MySQL时,遇到了InnoDB:Tablespace5975wasnotfound,该错误表明MySQL在启动过程中无法找到指定的s... 目录mysql 启动报错:InnoDB 表空间丢失问题及解决方法错误分析解决方案1. 启用 inno

在Java中基于Geotools对PostGIS数据库的空间查询实践教程

《在Java中基于Geotools对PostGIS数据库的空间查询实践教程》本文将深入探讨这一实践,从连接配置到复杂空间查询操作,包括点查询、区域范围查询以及空间关系判断等,全方位展示如何在Java环... 目录前言一、相关技术背景介绍1、评价对象AOI2、数据处理流程二、对AOI空间范围查询实践1、空间查

MySQL表空间结构详解表空间到段页操作

《MySQL表空间结构详解表空间到段页操作》在MySQL架构和存储引擎专题中介绍了使用不同存储引擎创建表时生成的表空间数据文件,在本章节主要介绍使用InnoDB存储引擎创建表时生成的表空间数据文件,对... 目录️‍一、什么是表空间结构1.1 表空间与表空间文件的关系是什么?️‍二、用户数据在表空间中是怎么

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三

CentOS7增加Swap空间的两种方法

《CentOS7增加Swap空间的两种方法》当服务器物理内存不足时,增加Swap空间可以作为虚拟内存使用,帮助系统处理内存压力,本文给大家介绍了CentOS7增加Swap空间的两种方法:创建新的Swa... 目录在Centos 7上增加Swap空间的方法方法一:创建新的Swap文件(推荐)方法二:调整Sww

Java遍历HashMap的6种常见方式

《Java遍历HashMap的6种常见方式》这篇文章主要给大家介绍了关于Java遍历HashMap的6种常见方式,方法包括使用keySet()、entrySet()、forEach()、迭代器以及分别... 目录1,使用 keySet() 遍历键,再通过键获取值2,使用 entrySet() 遍历键值对3,

查看Oracle数据库中UNDO表空间的使用情况(最新推荐)

《查看Oracle数据库中UNDO表空间的使用情况(最新推荐)》Oracle数据库中查看UNDO表空间使用情况的4种方法:DBA_TABLESPACES和DBA_DATA_FILES提供基本信息,V$... 目录1. 通过 DBjavascriptA_TABLESPACES 和 DBA_DATA_FILES