二叉树02.深度优先遍历之Morris遍历
1. 概述 前一篇文章介绍了深度优先遍历的递归实现和迭代实现,这两种方式的时间复杂度都是O(n),空间复杂度都是O(h),本文将要介绍的 Morris 遍历的时间复杂度依然为O(n),但空间复杂度仅为O(1),其中 n 为节点数,h 为树的高度。 算法来历 1968年,《计算机程序设计艺术》的作者 Knuth 提出了一个问题:设计一个无需堆栈和额外标志域的非递归的中序遍历算法,且当遍历结束时树结构不变。此后,诞生了许多解决方案,而Morris 遍历是其中最优雅的一种(见参考资料[1])。 此算法由 Joseph M. MORRIS 在1979年的论文 "Traversing Binary Trees Simply and Cheaply"[2] 中首次提出。顺便再说一句,这个 MORRIS 正是大名鼎鼎的 KMP 算法的作者之一。 代码仓库:https://github.com/patricklaux/perfect-code 系列文章 (1) 深度优先遍历之递归和非递归遍历 (2) 深度优先遍历之 Morris 遍历【本文】 (3) 一种无需队列的层序遍历算法 IDDFS 2. 算法...
