私はバイナリツリーで問題を抱えています。問題が発生したとき、完全なバイナリツリーの最後のレベルで最も右のノードを見つけてください。ここで問題はO（n） O（n）でそれをすることは、すべての要素を横断することによって簡単ですが、O（n）よりも複雑ではない方法でこれを行う方法があります。インターネットを多用しています。物事について何かを得る。 ありがとうございます。完全なバイナリツリーの最後のレベルで最も右のノードの位置を見つける方法は？
これは完全なバイナリツリーなので、右のノードに到達するまですべての右ノードを通過すると、O（N）ではなくO（logN）になります。正規のバイナリツリーでは、最悪の場合、すべてのノードが右に並んでいるので、完全なバイナリツリーであるため、O（N）をとります。
これはO （n） '。 – amit
TomerSHは、すべてのノードを訪問し、より良い方法を求めていると言っています。 –
はい、これはO(log(n)^2)バイナリ検索のバリエーションを実行します。
これは、最初に左の要素に移動し、次に2番目の左端の要素に、次に4番目の左端の要素8番目に移動して、そのような要素が見つからなくなるまで実行できます。 見つかった最後の要素がi番目で、最初に2iでなかったとします。
これで、その範囲で簡単にバイナリ検索ができます。
これは合計反復数であり、各反復はツリー全体になりますので、合計はO(log(n)^2)です。
（1）ここで、「xの最も左の要素」は、ツリーの最も深いレベルのノードのみを参照しています。
あなたはノードの数を知っていると仮定します。そのような数字をnとしましょう。
完全なバイナリツリーでは、レベルiはレベルi - 1より2倍のノード数を持っています。
したがって、nを反復して2に分けることができます。余りがある場合nは右の子です。そうでなければ、左の子です。余りがあるかどうかにかかわらず、シーケンス、好ましくはスタックに格納します。一部など
：
Stack<char> s;
while (n > 1)
{
if (n % 2 == 0)
s.push('L');
else
s.push('R');
n = n/2; // n would int so division is floor
}
while終了すると、スタックは、右端のノードへのパスを含みます。
whileが実行された回数は、log_2(n)です。
これをスタックに追加するとO（n）時間がかかるため、この時間は重要ではありません。 –
@aswin mythiliではありません。スタックへの挿入はO（1）です。リストまたはベクトルを使用することもできます。時間は挿入の数に制限されています。これは 'log_2（n）'です。 – lrleon
ツリー内の全ノード数を保存しておけば、左ブランチまたは右ブランチをいつ訪れるか正確に分かっているのでO（logN）です –