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

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. 使用一个栈来保存还未遍历完的节点。
2. 每次取出栈顶元素进行遍历，并将其左右子节点加入栈中。

通过这种方式，可以避免队列中保存大量节点从而导致内存超出限制的问题。

示例代码：

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            ans.push_back(node->val);
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
        return ans;
    }
};

总结：

使用迭代方式遍历树并使用栈来保存未遍历节点可以有效地解决二叉树层序遍历中出现的内存超出限制问题。在处理大型树结构时，建议优先考虑使用迭代方法，以避免内存溢出。