C++ 二叉树层序遍历代码分析与优化

C++ 二叉树层序遍历代码分析与优化

以下代码实现二叉树的层序遍历：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        deque<TreeNode*> q;
        int deep=0;
        if(root) q.push_back(root);
        while(!q.empty()){
            for(int i=0;i<q.size();i++){
                ans[deep].emplace_back(q[i]->val);
            }            
            TreeNode* p=q.front();
            q.pop_front();
            if(p->left) q.push_back(p->left);
            if(p->right) q.push_back(p->right);
            deep++;
        }
        return ans;
    }
};

代码中的问题：

代码中的问题是没有为每一层的vector在ans中分配空间，需要在while循环中加入ans.emplace_back(vector<int>())。

优化后的代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        deque<TreeNode*> q;
        int deep=0;
        if(root) q.push_back(root);
        while(!q.empty()){
            ans.emplace_back(vector<int>()); // 为每一层分配空间
            for(int i=0;i<q.size();i++){
                ans[deep].emplace_back(q[i]->val);
            }            
            TreeNode* p=q.front();
            q.pop_front();
            if(p->left) q.push_back(p->left);
            if(p->right) q.push_back(p->right);
            deep++;
        }
        return ans;
    }
};

优化原理：

在优化后的代码中，我们在while循环开始处使用ans.emplace_back(vector<int>())为每一层分配一个空的vector。这样，在后续的循环中，我们就可以将该层的节点值添加到对应的vector中，避免了越界访问错误。

通过以上分析和优化，我们修正了代码中的错误，并确保代码能够正确实现二叉树的层序遍历功能。