algorithm - Morris中序树遍历算法的运行时间

Question

我刚刚了解了 Morris 中序树遍历算法。但是我没有找到任何关于这个算法的运行时间的分析。有人可以对此算法进行运行时分析吗？这个链接解释了莫里斯算法是如何工作的。谢谢~~ 解释Morris中序树遍历不使用堆栈或递归

Answer 1

那可能是因为它很容易推断。每次访问都有固定的工作量。没有节点被访问超过 3 次（对于二叉树），所以它通常是 O(n)，其中 n 是节点数。