102.二叉树的层序遍历

【LetMeFly】102.二叉树的层序遍历 + 针对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$层

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

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

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

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

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

详见代码注释。

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

AC代码

C++

typedef pair<TreeNode*, int> pii;
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root)  // root本来就为空
            return {};
        queue<pii> q;  // 队列
        int lastLayer = 0;  // 上一个节点是第几层
        q.push({root, 0});
        vector<vector<int>> ans;  // 答案
        vector<int> 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;
    }
};

方法二：层次遍历 + 针对C++的使用空间优化

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

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

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

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

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

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

AC代码

C++

typedef pair<TreeNode*, int> pii;
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root)
            return {};
        int lastLayer = 0;
        queue<pii> q;
        q.push({root, 0});
        vector<vector<int>> 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;
    }
};

方法三：更简单点的方法（不需要将“那一层”的信息入队）

我们只需要将节点入队，当队列非空时：

假如当前队列的大小为$size$，那么就一共循环$size$次，并作为一层加入到答案中。

AC代码

C++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if (root) {
            q.push(root);
        }
        while (q.size()) {
            ans.push_back({});
            for (int i = q.size(); i > 0; i--) {
                TreeNode* thisNode = q.front();
                q.pop();
                ans.back().push_back(thisNode->val);
                if (thisNode->left) {
                    q.push(thisNode->left);
                }
                if (thisNode->right) {
                    q.push(thisNode->right);
                }
            }
        }
        return ans;
    }
};

Python

# from typing import List, Optional

# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        q = []
        if root:
            q.append(root)
        while q:
            ans.append([])
            for _ in range(len(q)):
                thisNode = q[0]
                q = q[1:]
                ans[-1].append(thisNode.val)
                if thisNode.left:
                    q.append(thisNode.left)
                if thisNode.right:
                    q.append(thisNode.right)
        return ans

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

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