L102 二叉树的层序遍历

/**
 * 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*> nodequeue; // 创建结点队列
            vector <int> levelsize; // 维护每一层的结点数量

            nodequeue.push(root); //把头结点放入队列
            levelsize.push_back(1); //把第0层大小设置为1

            vector <vector <int>> ans; //返回结果
            vector <int> ans_level; //每一层的结果
            
            if(root == nullptr) //根结点为空的情况
                return ans;

            int i = 0; //表示层数

            while(!nodequeue.empty()) // 队列不为空就循环,i 表示层数，初始为第0层
            {
                TreeNode *now_node = nodequeue.front(); //取队首
                nodequeue.pop(); //出队
                
                ans_level.push_back(now_node->val); // 当前结点值放入本层结果

                if(now_node->left) //存在左子结点
                {
                    nodequeue.push(now_node->left); //入队

                    //下一层计数
                    if(i == levelsize.size() - 1) //如果不存在下一层
                        levelsize.push_back(1); //创建下一层并初始化为1
                    else
                        levelsize[i+1]++;

                }
                if(now_node->right) //存在右子结点
                {
                    nodequeue.push(now_node->right); //入队

                    //下一层计数
                    if(i == levelsize.size() - 1) //如果不存在下一层
                        levelsize.push_back(1); //创建下一层并初始化为1
                    else
                        levelsize[i+1]++;
                }

                levelsize[i]--; //当前层的数量减一
                if(levelsize[i] == 0) //这一层已经全部处理完了，则可以开启下一层
                {
                    ans.push_back(ans_level); //把这一层的结果放回到输出结果中
                    ans_level.clear();

                    if(i == levelsize.size() - 1)//如果没有下一层了
                        break;

                    else //如果存在下一层
                        i++;
                }
            }

            return ans;
        }
};

class Solution 
{
    public:
        vector<vector<int>> levelOrder(TreeNode* root) 
        {
            vector <vector<int>> ans; //返回结果
            if (!root) return ans;  //考虑头结点为空

            queue <TreeNode*> nodequeue; //创建结点队列
            nodequeue.push(root); //放入头结点

            while (!nodequeue.empty()) //结点队列不为空，则遍历队列
            {
                int sz = nodequeue.size(); //sz保存当前队列长度，每一次while都是新的一层，因此也是本层的数量
                vector <int> ans_level; //当前层的结果

                for (int i = 0; i < sz; i++)
                {
                    TreeNode* now_node = nodequeue.front(); //取队首
                    nodequeue.pop(); //出队
                    ans_level.push_back(now_node->val); //放回返回结果

                    if (now_node->left)  nodequeue.push(now_node->left);
                    if (now_node->right) nodequeue.push(now_node->right);
                }
                ans.push_back(ans_level);
            }
            return ans;
        }
};