102. 二叉树的层序遍历

题目链接

解题思路

• 层序遍历就是用队列，本题需要一层一层收集答案，所以我们可以用一个变量cur，表示该层还剩多少节点需要收集，同时，遇到一个节点，还要将其孩子节点放入队尾。那么我们怎么知道下一层的节点个数，所以还需要一个变量next，记录下一层的节点个数。

• 总结一遍：每次从队头拿出一个节点A，然后把孩子节点放入队尾，每当有一个孩子节点，next++，然后cur--，如果cur == 0代表这一层的答案已经收集完毕，所以可以跳到下一层，即cur = next; next = 0;。

• 代码

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   * };
   */
  class Solution {
  public:
      vector<vector<int>> levelOrder(TreeNode* root) {
          vector<vector<int>> ans;
          if (root == nullptr) {
              return ans;
          }
          int cur = 1;
          deque<TreeNode *> deq;
          deq.push_back(root);
          int next = 0;
          vector<int> tmp;
          while(!deq.empty()) {
              TreeNode *cur_node = deq.front();
              deq.pop_front();
              if (cur_node->left != nullptr) {
                  deq.push_back(cur_node->left);
                  next++;
              }
              if (cur_node->right != nullptr) {
                  deq.push_back(cur_node->right);
                  next++;
              }
              tmp.push_back(cur_node->val);
              cur--;
              // 本层结束了
              if (cur == 0) {
                  ans.push_back(tmp);
                  tmp.clear();
                  cur = next;
                  next = 0;
              }
          }
          return ans;
      }
  };