-1

BSTのレベルごとの最大要素を見つけます。

[1] In O(n) time and O(1) space
[2] In O(logn) time and O(n) space

編集：@Imposterによって投稿されたソリューションは[1]で正常に機能します[1]のソリューションは次のとおりです

private int level = 0;
private int VisitedLevels = -1;

public void findLargestByLevel(AvlNode root)
{
    if(root == null) return;

    else
    {
        if(level > VisitedLevels)
        {
            System.out.println(root.data + " @ Level = " + level);
            VisitedLevels++;
        }
        level++;

        findLargestByLevel(root.right);
        findLargestByLevel(root.left);

        level--;
    }
}

しかし、私はまだ[2]の解決策を見つけることができません

私が考えたアプローチ：ツリーを前処理し、ツリーのシリアル化のようにフラット化すると、

                 100
             50         200
         20      75

#L0, 100, #L1, 50, 200, #L2, 20, 75, #L3

#Lがレベルのマーカーである場合：

そうすれば、O（1）時間でレベルの最高と最低のクエリに簡単に答えることができます。また、ツリーが変更された場合、LogN時間でシリアル化されたデータの挿入と削除を実行できます。[2]について誰かを提案してください。私の意見では、zitは[2]を達成するのは不可能に見えますが、他の人の提案を聞きたいです。

4

2 に答える 2

6

BSTがフルBSTの場合、常に右に向かってトラバースするだけなので、log（N）時間で実行できます（右側の要素は常に左側よりも大きいため）。フルBSTでない場合次に、右側のサブツリーの高さが常に左側のサブツリーよりも大きいかどうかわからないため、すべての要素をトラバースする必要があります。

例：右のサブツリーに2つのレベルがあり、左のサブツリーに3つのレベルがある場合、上記のアプローチを使用すると、2つのレベルまで最大値を出力できますが、右のサブツリーに存在しない3番目のレベルを見逃しました。

したがって、時間計算量は、フルBSTでない場合は最小O（n）になり、余分なスペースが指定されていない場合はさらに大きくなる可能性があります。

BFSを実行する場合、O（n）時間計算量とO（n）空間計算量のみが必要です。DFSを使用して必要な場合は、次のアルゴリズムがO（n）時間計算量、およびO（h）で役立ちます。ここで、hはツリーの高さです。

トラバース中のこれまでのレベルの最大数を示すグローバル変数カウンターを取得します。

左のサブツリー増分Lを再帰的に呼び出すときは、常に2つの変数LとRを取ります。

同様に、右のサブツリー増分Rを再帰的に呼び出す場合も同様です。

レベル番号を与える各ノードのLとRの最大値を見つけます。

トラバース中にノードのmax（ L、R ）にインクリメントがある場合は常に、カウンターがmax（ L、R ）未満の場合はカウンターでこれを確認し、メモリを割り当ててゼロに初期化し、カウンターをインクリメントします（つまり、実際に作成していますツリーの各レベルの変数）。

トラバース中、毎回高さまたはレベル変数をチェックし、現在のノードがレベル変数よりも大きい場合は考慮されている現在のノードと比較し、考慮されているノードでレベル変数を更新します。

トラバーサル後の印刷の高さまたはレベル変数。

于 2012-09-21T06:45:38.267 に答える
-1

[1]これは、各レベルを通過し、最大値を記録することによって繰り返し実行できます。これは、単純なBFSで実行できます（ストレージ内でも再帰レベル変数をカウントしないと仮定します）。たとえば。再帰を単純なキューに置き換えると、O（1）ストレージよりもコストがかかります。この場合、ノードがレベルごとにソートされていない限り、これは不可能に思えます。

[2]二分木には、右の子が左よりも大きいという特性があるため、毎回右端の子をトラバースする場合（存在しない場合を除き、左の子を取得）、log（n）時間で最大値を取得できます。O（n）ストレージが必要かどうかはわかりません。

于 2012-09-21T05:29:26.443 に答える