力扣102. 二叉树的层序遍历（复习vector和queue的常见用法

题目描述

题目解析

题目答案

题目所用知识点

最后

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

使用队列来暂存每一层的节点，通过读取队列中的节点来遍历它的下一层节点。每一层节点的个数由levelSize来确定，以循环的形式依次遍历。当每次levelSize减为0时，此时queue中只剩余下一层的节点，据此重新赋值levelSize，当queue不为空时依次循环遍历。

题目答案

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;

        if (root == nullptr)
        {
            return vv;
        }

        int levelSize = 1;
        queue<TreeNode*> qu;
        qu.push(root);

        while (!qu.empty()) {
            vector<int> v;
            while (levelSize--) {
                TreeNode* tmp = qu.front();
                qu.pop();
                v.push_back(tmp->val);

                if (tmp->left != nullptr) {
                    qu.push(tmp->left);
                }
                if (tmp->right != nullptr) {
                    qu.push(tmp->right);
                }
            }
            levelSize = qu.size();
            vv.push_back(v);
        }
        return vv;
    }
};