力扣上题求解（二叉树层序遍历）

Question

class Solution {

    vector<vector<int>>vct;
    queue<TreeNode *> que;
    int size=0;
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==nullptr)
            return vct;
        que.push(root);
        while(!que.empty())
        {   
            vector<int> V;
            size=que.size();

            while(size!=0)
            {
                struct TreeNode *p=que.front();
                
                V.push_back(p->val);
                que.pop();
                size--;
                if(root->left!=nullptr)
                    que.push(root->left);
                if(root->right!=nullptr)
                    que.push(root->right);
            }
            vct.push_back(V);
        }
        return vct;
    }
};

问题是显示我超出内存限制？请问是哪里出问题了

Answer 1

🕒上午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：时间是最好的医生，但也是最坏的美容师。” — 乔治·肖

在你的 C++ 代码中，出现超出内存限制的问题，主要是因为在层序遍历二叉树时，你在处理队列中的节点时，错误地使用了 root 来访问子节点，而不是使用当前节点 p。这导致了无限循环，因为你总是将根节点的子节点推入队列，而不是当前节点的子节点。

以下是修正后的代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vct; // 存储结果
        if (root == nullptr) {
            return vct; // 如果根节点为空，返回空结果
        }

        queue<TreeNode*> que; // 创建队列
        que.push(root); // 将根节点入队

        while (!que.empty()) {
            vector<int> V; // 存储当前层的节点值
            int size = que.size(); // 当前层的节点数

            for (int i = 0; i < size; i++) { // 遍历当前层的所有节点
                TreeNode* p = que.front(); // 获取队首节点
                que.pop(); // 出队
                V.push_back(p->val); // 将节点值加入当前层的结果

                // 将当前节点的子节点入队
                if (p->left != nullptr) {
                    que.push(p->left);
                }
                if (p->right != nullptr) {
                    que.push(p->right);
                }
            }
            vct.push_back(V); // 将当前层的结果加入最终结果
        }
        return vct; // 返回最终结果
    }
};

主要修改点：

1. **使用当前节点 p**：

   • 在遍历子节点时，使用 p->left 和 p->right，而不是 root->left 和 root->right。这样可以确保你在处理当前节点的子节点，而不是总是处理根节点的子节点。

2. 使用 for 循环：

   • 使用 for 循环来遍历当前层的所有节点，简化了代码并提高了可读性。

代码逻辑：

• 首先检查根节点是否为空，如果为空，直接返回空的结果。
• 使用队列来进行层序遍历，首先将根节点入队。
• 在每一层中，记录当前层的节点数，然后遍历这些节点，将它们的值存入结果向量，并将它们的子节点入队。
• 最后返回结果。

这样修改后，代码应该能够正确地进行二叉树的层序遍历，而不会出现超出内存限制的问题。希望这能帮助你解决问题！