morris遍历的空间复杂度

楼主在做 145 题 二叉树后向遍历的时候，看到有一种 空间复杂度为 O(1) 的方法叫 morris 遍历。我可以理解 morris 遍历本身，如果只是访问到目标节点并 print 出来的话，是 O(1) 的空间。但是在看到网上很多题解，以及本题要求，都是要最后以一个 list 输出结果。那这样的话，由于 结果 list 占的空间，岂不是任何算法的空间复杂度最小是 O(n)? 还是说，楼主对空间复杂度这个概念的理解有偏差，还望大神们不吝赐教！感谢~

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/

lz你好，morris的空间复杂度O(1)指的是，在便利过程中不需要依靠stack(or recursive stack)或者其他数据结构来维护遍历顺序。

并且一般我们讨论遍历的空间复杂度，一般不考虑输出空间占用。

您可以这么想：很多Online Judge的输出并不是一个list 而只是让你print出遍历结果到stdout。这么算的话用Morris就是O(1)空间。但是如果用普通遍历的话，依然需要耗费O(height)的空间用作stack或者recursion stack。

timzyt 发表于 2021-7-28 12:42
lz你好，morris的空间复杂度O(1)指的是，在便利过程中不需要依靠stack(or recursive stack)或者其他数据结 ...

感谢！ 那么可不可以认为，在分析leetcode题目的空间复杂度的时候，考虑的都是中间过程用到的数据结构的复杂度，而不去考虑输出（如果输出是bottleneck的话）？

王晓枫 发表于 2021-7-28 13:43
感谢！ 那么可不可以认为，在分析leetcode题目的空间复杂度的时候，考虑的都是中间过程用到的数据结构的 ...

嗯。我觉得可以这么说。
但是面试的时候还是要跟面试官声明。