Morris inorder树遍历算法的运行时间

Question

我刚刚了解了Morris inorder树遍历算法。但是我还没有发现这个算法的运行时间的任何分析。有人可以给这个算法的运行时分析吗？这个链接解释了Morris算法的工作原理。谢谢~~ Explain Morris inorder tree traversal without using stacks or recursion

Answer 1

这可能是因为它是如此简单的推论。每次访问都有相当数量的工作。没有节点访问超过三次（对于二叉树），所以它是平凡的O（n），其中n是节点的数量。