如何在不使用递归的情况下获取二叉树的最小高度

Question

我已经坚持了一段时间了。这就是我到目前为止所拥有的，但它给出了错误的结果。

int get_min_height_iter(Node* r) {
    if (!r) return 0;
    std::queue<Node*> queue;
    queue.push(r);
    int count = 1;
    while (!queue.empty()) {
        Node* temp = queue.front();
        queue.pop();
        if (!temp->left || !temp->right)
            return count;
        ++count;
        queue.push(temp->left);
        queue.push(temp->right);
    }
    return -1;
}

请注意，我已经可以使用递归来执行此函数，我对使用队列或堆栈特别感兴趣。我还可以获得树的最大高度;我现在需要创建一个函数来获得最小高度。

例如，在这种情况下，函数应返回 3，但它返回 2：

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->left->right->left = new Node(5);
    root->right->right = new Node(6);
    cout << get_min_height_iter(root);
    cin.get();
}

我知道它为什么要这样做，我使用调试器跟踪代码，但我对二叉树没有太多经验，我不知道如何修复它。提示将不胜感激！

Answer 1

您有三四个问题：

1. 您需要将每个节点的秩（深度）与节点本身一起推送到队列中。 如果您没有其他地方的位置，您可以使用std::pair<>来捆绑该信息。 如果节点结构具有"深度"或"秩"成员，则只需更新即可。
2. 您的问题陈述要求您测量深度，而不是计算节点数。 给定节点的深度等于其父节点的深度加 1。 您的循环当前对节点进行计数。
3. 仅将子项推送到队列中（如果存在）。
4. 如果最小深度被指定为到没有后代的节点的最短路径，那么您的"if （） return"条件应该寻找左和右为空，而不是左或右为空。