[数据结构与算法]leetcode102. Binary Tree Level Order Traversal

题目：题目链接

这题其实我开始想用dfs的，设置深度，然后根据深度判断它们是否在同一层，但我发现二维的vector设置就很浪费空间，而且搜索的时候可能次序不一样，所以休息了一下午。
晚上就突然间有头绪了，因为二叉树的层次遍历是用队列嘛，所以就考虑用队列去做。
具体做法：先将根节点放入队列，然后依次拓展左右节点。在一个层的节点拓展前记录当前队列大小，其实也就是该层的节点个数。之后弹出这些节点，在对后面加入的节点重复操作就可以了。
看代码吧直接：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        vector<vector<int> > ans;
        queue<TreeNode*>q;
        q.push(root);
        int cnt = 0;
        vector<int>tmp;
        while (!q.empty()) {
            cnt = q.size();
            while (cnt-- > 0) {
                TreeNode* ele = q.front();
                tmp.push_back(ele->val);
                if (ele->left != nullptr) 
                    q.push(ele->left);
                if (ele->right != nullptr) 
                    q.push(ele->right);
                q.pop();
            }
            ans.push_back(tmp);
            tmp.clear();
        }
        return ans;
    }
};

这就ok了，一道需要捋一下的题目吧。