非递归程序来查找二叉树的最小高度

Question

我知道可以编写递归代码来查找最小高度。但是对于一个非常大的树（比如左侧的百万节点与右侧的 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
              /  
             2    3
             /
            4
            /
            6

以上返回 1，（根据地板（Log（n））？

谢谢。

Answer 1

这个想法是完美的。但是代码仍然可以改进一点。

1. 为什么每次取消排队项目时都会增加最小值？你做两次，:)差两倍如果您将此变量作为节点计数器，那么它也不正确，因为您没有计算根元素。因此，它必须以另一种方式调用，而不是最小值。
2. 为什么要检查孩子是否为空两次？如果语句破坏了管道，则必须将其计数最小化。

接下来是这个想法。让我们将相同级别的节点行称为 full 如果其中的每个节点都有两个子节点。则最小高度是树中整行的计数。它等于最接近所有整行中的项目计数的功率指数 2 + 1。代码：

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; // :)

Answer 2

使用 2 个堆栈执行"之字形"遍历。计算您需要翻转"从左到右"标志的次数。