binary-tree - 二分木の最小の高さを見つけるための非再帰的プログラム

Question

最小の高さを見つけるために再帰的なコードを書くことができることを私は知っています。しかし、非常に大きなツリー（左側に100万ノード、右側に1ノードなど）の場合、このアプローチは適切ではありません。したがって、次のコードで問題がない場合は、BFSを使用していることをお知らせください。-

    if (root == null)
    {
        return 0;
    }

    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(root);
    int min = 0;

    while (queue.Count > 0)
    {                
        Node temp = queue.Dequeue();

        if (temp.LeftChild == null)
        {
            return ++min;
        }
        if (temp.LeftChild != null)
        {
            ++min;
            queue.Enqueue(temp.LeftChild);
        }

        if (temp.RightChild == null)
        {
            return ++min;
        }
        if (temp.RightChild != null)
        {
            ++min;
            queue.Enqueue(temp.RightChild);
        }
    }

    return 0;

だから、のような木のために

上記は1を返します（Floor（Log（n））に従って？

ありがとう。

score 1 · Accepted Answer

アイデアは完璧です。しかし、コードはまだ少し改善することができます。

アイテムをデキューするたびに最小値を増やすのはなぜですか？そして、それを2回実行すると、2倍悪化します:)この変数がノードカウンターであると仮定すると、ルート要素をカウントしなかったため、これも正しくありません。したがって、 minではなく、別の方法で呼び出す必要があります。
なぜ子が2回nullかどうかをチェックするのですか？ステートメントがパイプを台無しにする場合は、その数を最小限に抑える必要があります。

次のアイデアです。その中のすべてのノードに両方の子がある場合、同じレベルのノードの行をフルと呼びましょう。次に、最小の高さは、ツリー内の完全な行の数です。これは、すべての全行のアイテム数+1に最も近いパワーインデックス2に等しくなります。コード：

if (root == null)
{
    return 0;
}

Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
int nodesCount = 0;

while (queue.Count > 0)
{                
    Node temp = queue.Dequeue();

    if (temp.LeftChild == null || temp.RightChild == null)
    {
        return Floor(Log(nodesCount + 1)/Log(2)); // It can be made much better using, for example, bitwise operations but this is not the question`s topic
    }

    ++nodesCount;
    queue.Enqueue(temp.LeftChild);
    queue.Enqueue(temp.RightChild);
}

return Infinity; // :)

score 0 · Accepted Answer

2つのスタックを使用して、「ジグザグ」トラバーサルを実行します。「leftToRight」フラグを反転する必要がある回数を数えます。

binary-tree - 二分木の最小の高さを見つけるための非再帰的プログラム

2 に答える 2

Related

Reference