广州建站模板平台搜狗网站

✨✨ 欢迎大家来到小伞的大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：C++_OJ
小伞的主页：xiaosan_blog

二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

解题思路：

由于树中节点数目在范围 [0, 2000] 内，空间需求量小，为了预防内部插入时，还需对空间的判断，在主函数中，开辟（2000*(int)）的空间。

vector<vector<int>> s;

        s.resize(2000);

由于题目要求存放在 vector<vector<int>>二维数组中，我们需要一个变量level控制存放位置,因为resize的原因，最后我们是要释放掉没有使用的空间，所以创建size变量存放树的高度；

class Solution {

public:

    void rootlevel(TreeNode* root, int level(控制存放位置), vector<vector<int>>& s,int& size(计算树的高度)(需要是全局变量或者指针变量)) {

        if (root == nullptr) {

            return;

        }

        s[level].push_back(root->val);

        rootlevel(root->left, ++level, s, size);//由于左子树与右子树为同一层

        rootlevel(root->right, level, s, size);//所以++level后右子树不必++

        size = size >= level ? size : level;//记录树的高度

    }

    vector<vector<int>> levelOrder(TreeNode* root) {

        vector<vector<int>> s;

        s.resize(2000);//对于空间需求量小，提前开好空间，不必对空间进行判断

        int size = 0;

        rootlevel(root, 0, s, size);

        s.resize(size);//释放掉不需要的空间

        return s;

    }

};