102-二叉树的层次遍历

使用队列实现
思路：

1. 将根节点的指针插入到队中
2. 当队列不为空则（循环）
   队首元素出栈，并访问其指向的节点
   若当前节点的左/右孩子不为空，则将其指针依次入队

代码如下：

class Solution
{
public:
  vector> levelOrder(TreeNode *root)
  {

      // 声明一个用于保存结果的二维数组
      vector> ret;
      if (!root)
      {
          return ret;
      }
      // 定义一个队列
      queue q;
      q.push(root);

      // 1. 将根节点指针插入队列
      // 怎么记录它的层次？
      while (!q.empty())
      {
          int currentLevelSize = q.size(); // 当前队列的长度
          ret.push_back(vector());    // 向二位數組中插入一個空的
          // 这里是怎么保证二叉树每一层的？
          for (int = 1; i <= currentLevelSize; ++i)
          {
              auto node = q.front();
              q.pop();

              ret.back().push_back(node->val);
  			// 因爲ret是一个二维数组，所以back返回的是一个一维数组
              if (!node->left.empty())
              {
                  q.push(node->left);
              }
              if (!node->right.empty())
              {
                  q.push(node->right);
              }
          }
      }
      return ret;
  }
};

没搞懂的点有两个：

1. 虽然知道了思路，但是不知道为什么要这么做、为什么这样做是正确的
2. currentLevelSize变量是怎么配合for循环实现将二叉树的每一层正确地输出到二维数组中的