leetcode 102.二叉树的层序遍历

这道题讲的就是对于树的数据结构的考察，这里用了一个比较常用的容器就是队列。

思路：首先我们知道，层序遍历也就是广度优先遍历的一种变形而已，既然我们知道广度优先搜索，就应该知道用队列进行辅助输出。

当根节点是不存在的时候，那么就直接返回空数组就行了。

当根节点是存在的时候，我们就首先把根节点放入到队列当中。然后就开始进入一个循环：当队列不是空的时候，我们就开始遍历输出。因为队列里面有可能有很多结点，所以我们不一定就直接O（1）的方法来进行遍历，所以我们只能进行for循环进行遍历。我们需要知道队列的数目，所以需要用一个变量进行代替，这个循环就在这个队列当中遍历。

当我们开始对一个节点进行访问的时候，别忘记在访问的时候i把其踢出队列，防止重复访问。我们需要知道它是否有左子树或者说是右子树，有一个，两个还是都没有，我们需要判断一下。从左子树开始判断，再判断右子树，有的话就直接进入队列方便下次的遍历；如果没有就没有，不用做任何操作。

就这样进行循环完成之后，返回数组就行了。

注意：这里用的vector<vector<int>>数组，所以一开始是什么都没有的，所以需要在进行二维插入时候我们有一个操作就是：haha.push_back(vector<int>())，这样我们在进行二维的插入的时候才有空间可用。另外一点，我们没必要用数组的形式（比如haha[n].push_back())进行操作，我们可以随着循环的进行，一个一个插入。因此，我们用haha.back().push_back()就行了。

上代码：

/**
 * 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) {
        queue<TreeNode*>q;
        vector<vector<int>>haha;
        int k=0;
        if(!root)
        return haha;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            haha.push_back(vector<int>());
            for(int i=0;i<size;i++){
                TreeNode*res=q.front();
                haha.back().push_back(res->val);
                q.pop();
            if(res->left)
            {
                q.push(res->left);
            }
            if(res->right){
                q.push(res->right);
            }
            }
        }
        return haha;
    }
};