如何解决Level Order Traversal Problem（二叉树）的无限循环错误

Question

教授提供了这段代码，但我一直在无限循环。我也不理解for循环中带有“：”的auto关键字。

我似乎无法理解bug的位置。

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;
}