目录

题干

解题思路

  总结与反思

---

题干

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

解题思路

层序遍历一个二叉树，就是从左到右一层一层的去遍历二叉树。我们需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑。

我们把根节点入队列 ，把根节点放入第一层的数组，再放入结果数组，将根节点的左右节点放入队列（空节点不入栈），将根节点从队列中弹出。现在队列里面包含了下一层所有的节点，为了遍历，我们需要计算队列的大小，然后遍历队列将每个元素放入这一层的数组，把左右节点入队列，弹出当前节点，遍历完后，将这一层的数组放入结果数组。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
          vector<vector<int>> result;
          queue<TreeNode*> que;
          if(root != NULL){
            que.push(root);
          }
          while(!que.empty()){
            //建立每一层的数组
            vector<int> vec;
            // 如何判断每一层的个数
            //记录队列的大小
            int size = que.size();
            // 遍历队列，放入数组
             for(int i = 0; i < size; i++ ){
                //出队列第一个元素放入数组
                TreeNode* node = que.front();
                vec.push_back(node->val);
                //将左右节点入队列
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                //将当前节点弹出
                que.pop();
             } 
             // 将这一层的数组放入结果数组
             result.push_back(vec);
          }
    return result;
    }
};

  总结与反思

常见的错误 vector赋值方式

vector<int>a;
for(int i=0;i<10;++i){a[i]=i;}

因为下标只能用来获取已经存在的元素。

正确的写法是用 a.push_back(i)