题解 | 求二叉树的层序遍历

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

#include <vector>
class Solution {
  private:
    struct NodeLevel {
        TreeNode* ptr;
        int level;
        NodeLevel(TreeNode* ptr, int level): ptr(ptr), level(level) {}
    };
    queue<NodeLevel> que;
    vector<vector<int> > res;
  public:
    void visit(queue<NodeLevel>& node_que) {
        vector<NodeLevel> aans;
        int last_level = node_que.front().level;
        while (!node_que.empty()) {
            NodeLevel nodel = node_que.front();
            node_que.pop();
            if (nodel.ptr != nullptr) {
                aans.push_back(nodel);
                que.push(NodeLevel(nodel.ptr->left, nodel.level + 1));
                que.push({nodel.ptr->right, nodel.level + 1});
            }
        }
        int i = aans[0].level;
        vector<vector<int> > rs;
        for (auto nl : aans) {
            if (i == nl.level && i!=0) {
                rs[rs.size() - 1].push_back(nl.ptr->val);
            } else {
                vector<int> n;
                n.push_back(nl.ptr->val);
                rs.push_back(n);
                i = nl.level;
            }
        }
        res = rs;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        if(root==nullptr)return vector<vector<int>>();
        // write code here
        this->que.push(NodeLevel(root, 0));
        visit(this->que);
        return res;
    }
};