C++ 二叉树层序遍历 - 内存超出限制问题解决

C++ 二叉树层序遍历 - 内存超出限制问题解决

在使用 C++ 进行二叉树层序遍历时，可能会遇到内存超出限制的错误。这通常是因为在队列中加入了空指针，导致队列过大并最终超出了内存限制。

示例代码：

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root) q.push(root); // 判断根节点是否为空
        while(!q.empty()) {
            TreeNode* p = q.front();
            q.pop();
            ans.emplace_back(p->val);
            if(p->left) q.push(p->left); // 判断左子节点是否为空再加入队列
            if(p->right) q.push(p->right); // 判断右子节点是否为空再加入队列
        }
        return ans;
    }
};

问题分析：

在原始代码中，我们没有判断节点是否为空就将其加入队列。当遍历到叶子节点或空节点时，会将空指针加入队列，导致队列不断膨胀，最终导致内存超出限制。

解决方案：

为了解决这个问题，我们需要在加入节点之前判断节点是否为空。修改后的代码如下：

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root) q.push(root); // 判断根节点是否为空
        while(!q.empty()) {
            TreeNode* p = q.front();
            q.pop();
            ans.emplace_back(p->val);
            if(p->left) q.push(p->left); // 判断左子节点是否为空再加入队列
            if(p->right) q.push(p->right); // 判断右子节点是否为空再加入队列
        }
        return ans;
    }
};

总结：

通过在加入节点前判断节点是否为空，我们可以有效地避免空指针进入队列，解决内存超出限制的问题，确保程序的正常运行。

其他提示：

• 除了判断节点是否为空之外，还可以考虑使用其他数据结构，例如双端队列，来优化代码。
• 针对不同类型的树结构，可以根据实际情况调整代码，以提高效率。