Morris의 런타임 inorder 트리 순회 알고리즘

Question

모리스 인 오더 트리 순회 알고리즘에 대해 배웠습니다. 하지만이 알고리즘의 실행 시간에 대한 분석을 찾지 못했습니다. 누군가이 알고리즘에 대한 런타임 분석을 제공 할 수 있습니까? 이 링크는 Morris 알고리즘의 작동 원리를 설명합니다. 감사합니다 ~~ Explain Morris inorder tree traversal without using stacks or recursion

Answer 1

그것은 아마도 그렇게 쉽게 추론하기 때문입니다. 방문 할 때마다 일정한 작업량이 있습니다. 어떤 노드도 3 번 이상 (이진 트리의 경우) 방문하지 않으므로, O (n)은 노드 수입니다.