C++ 二叉树层序遍历：超出内存限制原因分析及优化

以下代码实现了 C++ 二叉树层序遍历，但可能会出现超出内存限制的问题。

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* p = root;
        while(!q.empty()) {
            if(p->left || p->right) {
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
            ans.emplace_back(q.front()->val);
            q.pop();
        }
        return ans;
    }
};

超出内存限制的原因：

1. 空根节点压入队列： 如果根节点为空，代码中的 q.push(root) 会将空节点压入队列，导致程序崩溃。
2. 树的深度过大： 如果二叉树的深度较大，队列中的节点数量可能会超出内存限制。

优化方案：

1. 处理空根节点： 在将根节点压入队列之前，需要判断根节点是否为空，如果为空则不压入队列。
2. 使用递归或其他方法： 对于深度较大的二叉树，可以使用递归或其他方法来解决问题，例如使用迭代器来遍历树的每一层。

优化后的代码：

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;  // 处理空根节点
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();  // 获取当前层的节点数量
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                ans.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ans;
    }
};

说明：

• 上面的代码使用了迭代器来遍历每一层节点，避免了队列中的节点数量过大。
• 使用 size = q.size(); 获取当前层的节点数量，可以在每次循环中遍历当前层的节点，从而避免了将下一层的节点提前压入队列。

通过以上优化，可以有效解决 C++ 二叉树层序遍历代码中出现的超出内存限制问题。