再帰のない平衡型バイナリ検索ツリーへの並べ替え済みの配列

Question

再帰および再帰を伴わない並べ替えられた配列からバランスの取れたバイナリ検索ツリーを構築するために、質問をしました。私は再帰を使用して解決策を考え出すことができましたが、再帰なしの解決策は出てこなかった。誰も再帰を使わずにこの問題の解決法を提供できますか？

Answer 1

独自のスタックを作成して使用することができます（配列やリンクリストなど）。ループ内からアクセスできます。

配列またはリスト内の各セルは、再帰関数によって維持されるツリーに関する重要な情報を格納する必要があります。

再帰バージョンの一部の情報（深さカウンタなど）は、代わりにローカル変数で扱うことができます。いくつかの問題については、すべての情報をスタックからローカル変数に移動することができます。そのような場合は、明示的なスタックを必要としません。