Как исправить эту ошибку бесконечного цикла для проблемы обхода порядка уровней (двоичные деревья)

Question

Профессор предоставил этот код, но я продолжаю получать бесконечный цикл.Я также не понимаю ключевое слово auto с циклом ":" в.

Кажется, я не понимаю, в чем заключается ошибка.

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    if (root == NULL)
        return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* curr = q.front();
            q.pop();
            if (curr->left != NULL) 
                q.push(curr->left);
            if (curr->right != NULL)
                q.push(curr->right);
            res.push_back(curr->data);
        }
    }
    return res;
}

...

int main () {
...
    vector<int> items = levelOrder(root);
    for (int item : items) {
        cout << item << " ";
    }
    cout << endl;
...
        return 0;
}

Infinite Loop

Answer 1

Во-первых, классический способ сделать обход уровня - использовать очередь, и ваш код делает это.

Однако вместо того, чтобы полагаться на состояние очереди для цикла с использованием условия while(!q.empty()), у вас есть совершенно ненужный и, вероятно, вредный внутренний цикл for. Если вы удалили внутренний цикл, то код должен работать правильно.

Пример:

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    if (!root)
        return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) 
    {
        TreeNode* curr = q.front();
        q.pop();
        if (curr->left) 
            q.push(curr->left);
        if (curr->right)
            q.push(curr->right);
        res.push_back(curr->data);
    }
    return res;
}