LeetCode 0102.二叉树的层序遍历 + 针对C++的使用空间优化 （可能不同于常规做法）

力扣题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/

给你二叉树的根节点 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 0 0层

我们用pair记录<此节点, 此节点的层数>

初始时将根节点入队，在队列不空的时候：

不断取出队首元素，如果此元素不空，就判断此元素和上一个元素是否在同一层

如果不在同一层，就把上一层的所有节点添加到答案中

把此节点的左右子入队（层数=此层+1）

详见代码注释。

• 时间复杂度 O ( N ) O(N) O(N)，其中 N N N是节点个数
• 空间复杂度 O ( N 2 ) O(N2) O(N2)，其中 N 2 N2 N2是节点最多的一层的节点数

typedef pair pii;
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if (!root)  // root本来就为空
            return {};
        queue q;  // 队列
        int lastLayer = 0;  // 上一个节点是第几层
        q.push({root, 0});
        vector> ans;  // 答案
        vector thisAns;  // 用来存放某一层的节点
        while (q.size()) {  // 不空的时候
            auto[p, thisLayer] = q.front();  // 取出队首元素
            q.pop();
            if (!p)  // 若为空节点，不做任何处理
                continue;
            if (thisLayer != lastLayer) {  // 这是新的一层
                lastLayer = thisLayer;  // 更新lastLayer
                ans.push_back(thisAns);  // 答案中添加这一层
                thisAns.clear();  // 这一层清空
            }
            thisAns.push_back(p->val);  // 添加到这一层中
            q.push({p->left, thisLayer + 1});  // 左子入队
            q.push({p->right, thisLayer + 1});  // 右子入队
        }
        ans.push_back(thisAns);  // 最后的一层添加到答案中
        return ans;
    }
};

不难发现，方法一中，vector thisAns用来记录这一层的节点。

当遇到新的一层的节点时，我们将````thisAnspush到了ans中，然后将thisAns```清空。

通俗地讲，就是先copy后删除。也许上述现象在某些语言中并不会发生，但C++中，确实会先为ans申请一些新的空间，再释放掉thisAns的空间，而不是直接让ans的下一个元素指向thisAns。

那么，我们如何避免上述现象呢？也很简单，只需要在ans中提前开辟一层，并且使用ans[ans.size() - 1]代替thisAns即可。

• 时间复杂度 O ( N ) O(N) O(N)，其中 N N N是节点个数。与方法一相比，不需要专门将“某一层”添加到答案中，也不需要清空“用于存储某一层的空间”
• 空间复杂度 O ( N 2 ) O(N2) O(N2)，其中 N 2 N2 N2是节点最多的一层的节点数。与方法一相比，优势在于没有专门为某一层申请临时存储空间

上述优化仅仅是个小优化，并不会改变复杂度。

typedef pair pii;
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if (!root)
            return {};
        int lastLayer = 0;
        queue q;
        q.push({root, 0});
        vector> ans;
        ans.push_back({});
        while (q.size()) {
            auto[p, thisLayer] = q.front();
            q.pop();
            if (!p)
                continue;
            if (thisLayer != lastLayer) {
                lastLayer = thisLayer;
                ans.push_back({});  // 这里不需要clear()了
            }
            ans[thisLayer].push_back(p->val);
            q.push({p->left, thisLayer + 1});
            q.push({p->right, thisLayer + 1});
        }
        // 这里也不需要push最后一层了
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125584554