题解 | #队列实现——求二叉树的层序遍历#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    void level_order(TreeNode* Node, vector<vector<int>>& ans) {
        if (Node == NULL) return;
        queue<TreeNode*> q;
        q.push(Node);
        while (!q.empty()) {
            vector<int> row; 
            int n=q.size();
            //由于返回值是一个二维数组，每一行是遍历的每一行，所以需要将每一层遍历的数据存放进一个数组，一层遍历完再将这个数组放入二维数组中。如果不用for循环，无法再queue中判断一行的结束，也就无法凑出二维数组
            for(int i=0;i<n;i++){
                TreeNode* temp = q.front();
                q.pop();
                row.push_back(temp->val);
                if (temp->left != NULL) q.push(temp->left);
                if (temp->right != NULL) q.push(temp->right);
            }
            ans.push_back(row);
        } 
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> ans;
        level_order(root, ans);
        return ans;
    }
};