一、题目[LeetCode-102]

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

二、思路

迭代-队列

由题意知，需要对数进行层次（序）遍历，可引入一个队列，维护树节点的访问顺序。开始时插入根节点入队列中。只要队列不为空，便取出一个队列头进行分析，先对其进行需要的操作，再将其子节点入队。本题中的“所需操作”即将节点的值插入一个二维数组中。

本题难点在于如何确定在队列中到底哪些节点属于同一层，从而将相同层的节点的值放入二维数组的同一行中。

这里可以利用队列的size()方法，在开始访问第i层的第一个节点之前，队列的size()便是第i层的节点数目。因此，可以在取出每层的第一个节点之前先套用一个for循环，循环次数即为q.size()。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;//返回结果的二维数组if (!root)return ans;//空节点的退化情况queue<TreeNode*> q;//引入一个队列，维护层次遍历（广度优先搜索）顶点访问次序q.push(root);//根节点入队while (!q.empty()){vector<int> levelNum;//声明一位数组用于存储当前层的值int n = q.size();for (int i = 0; i < n; i++)//当前层的节点个数即为q.size()，出了这个循环意味着进入下一层的遍历{TreeNode* t = q.front();//取出队首q.pop();levelNum.push_back(t->val);if (t->left)q.push(t->left);if (t->right)q.push(t->right);}ans.push_back(levelNum);}return ans;}
};

注意：for循环的写法细节：

int n = q.size();

for (int i = 0; i < n; i++)

这里先声明了n来存储q.size()，然后再在for循环中将i<n作为边界条件。为什么不可以直接

for (int i = 0; i < q.size(); i++)

呢？

因为在for循环中由于父节点的取出和子节点的插入，q.size()是动态变化的。而我们想要的循环次数是进行遍历取出该层第一个节点之前的size()，因此需要先用一个变量n来存储先前的q.size()。否则，如下图所示，可以细细品味。

 

 

三、官方题解（来源：力扣（LeetCode））

广度优先搜索

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用哈希表，维护一个以 level 为键，对应节点值组成的数组为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可。

考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？

我们可以用一种巧妙的方法修改广度优先搜索：

• 首先根元素入队
• 当队列不为空的时候

求当前队列的长度si

依次从队列中取si个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取si个元素。在上述过程中的第 i 次迭代就得到了二叉树的第 i 层的si个元素。

为什么这么做是对的呢？我们观察这个算法，可以归纳出这样的循环不变式：第 i 次迭代前，队列中的所有元素就是第 i 层的所有元素，并且按照从左向右的顺序排列。证明它的三条性质（你也可以把它理解成数学归纳法）：

• 初始化：i=1 的时候，队列里面只有 root，是唯一的层数为 1 的元素，因为只有一个元素，所以也显然满足「从左向右排列」；
• 保持：如果 i=k 时性质成立，即第 k 轮中出队sk的元素是第 k 层的所有元素，并且顺序从左到右。因为对树进行广度优先搜索的时候由低 k 层的点拓展出的点一定也只能是 k+1 层的点，并且 k+1 层的点只能由第 k 层的点拓展到，所以由这 sk个点能拓展到下一层所有的 sk+1个点。又因为队列的先进先出（FIFO）特性，既然第 k 层的点的出队顺序是从左向右，那么第 k+1 层也一定是从左向右。至此，我们已经可以通过数学归纳法证明循环不变式的正确性。
• 终止：因为该循环不变式是正确的，所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此，我们证明了算法是正确的。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;}
};作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

记树上所有节点的个数为 n。

• 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
• 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。