binary-tree - 非递归程序找到二叉树的最小高度

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，（根据 Floor(Log(n))？

谢谢。

Answer 1

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

1. 为什么每次出列项目时都会增加 min ？而且你做了两次，结果差了两倍 :) 如果你假设这个变量是节点计数器，那么它也是不正确的，因为你没有计算根元素。因此它必须以其他方式调用，而不是min。
2. 为什么要检查孩子是否为空两次？如果语句破坏了管道，则必须尽量减少它们的计数。

接下来是这个想法。如果其中的每个节点都有两个子节点，则我们称同级别节点的行已满。然后最小高度是树中完整行的计数。它等于最接近的幂指数 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 个堆栈进行“之字形”遍历。计算需要翻转“leftToRight”标志的次数。