树的遍历之Morris遍历 lf_Initative 发布于 2022-11-08 收录于 学习笔记有一种巧妙的方法可以在线性时间内,只占用常数空间来实现树的遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出,因此被称为 Morris 遍历。核心思想是利用树的大量空闲指针,实现空间开销的极限缩减(和线索二叉树底层原理相同)