algorithm - Morris 順序ツリー トラバーサル アルゴリズムのランタイム

Question

Morris の順序ツリー トラバーサル アルゴリズムについて学びました。しかし、このアルゴリズムの実行時間の分析は見つかりませんでした。誰かがこのアルゴリズムのランタイム分析を行うことができますか? このリンクでは、モリス アルゴリズムの仕組みについて説明しています。ありがとう~~ スタックや再帰を使わずにモリスの順序木トラバーサルを説明してください

Answer 1

それはおそらく、推測するのがとても簡単だからです。訪問するたびに一定量の作業があります。(バイナリ ツリーの場合) 3 回を超えてアクセスされるノードはないため、n はノードの数である O(n) です。