这次来写一下 LeetCode 的第 102 题 ， 二叉树的层次遍历 。
题目描述
题目直接从 LeetCode 上截图过来 ， 题目如下：
102.二叉树的层次遍历题目
上面的题就是 二叉树的层次遍历 题目的截图 ， 同时 LeetCode 会根据选择的语言给出一个类的定义或者函数的定义 ， 然后在其中实现 二叉树的层次遍历 的解题过程 。 这次我使用 C++ 语言来进行完成 。
C++ 语言给出的函数定义如下：
/** * Definition for a binary tree node. * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:vector> levelOrder(TreeNode* root) {}};通过函数定义可以看出 ， levelOrder 函数的参数是一个二叉树的根节点 ， 然后返回的值是一个二维数组 ， 我们要做的就是按照层次来遍历这个二叉树 ， 并且将二叉树每层的值需要保存在二维数组中并返回 。
问题分析
该题目是一个比较好理解的题目 ， 因为题目中已经明确了需要使用层次遍历二叉树来得到每个节点上的值 ， 且不同层次上节点的数据保存在不同的数组中 ， 最后每个层次的数组构成一个二维数组 。
拿题目中给出的例子来说明什么是层次遍历 ， 如下图 。
二叉树的层次
在图中 ， 3 是第一层 ， 9 和 20 是第二层 ， 15 和 7 是第三层 ， 通过遍历这个二叉树按层次来分别把它们保存到不同的数组中 ， 最后构成一个二维数组返回 。
二叉树的层次遍历需要使用另外一个数据结构来协助进行遍历 ， 另外的那个数据结构就是“队列” 。 队列的作用是保留每一层的从左到右的顺序 ， 进而使得我们在进行层次遍历的时候 ， 可以按照从左往右的顺序完成层次遍历 。
首先在遍历之前 ， 使根节点先进入队列 ， 队列中有了根节点后 ， 就可以进入循环 。 进入循环后 ， 首先获取队头的元素 ， 并让队头元素出队 ， 目前也就是根节点 ， 通过出队的元素分别得到它的左孩子和右孩子 ， 并让它的左孩子和右孩子进入临时队列（有可能左孩子和右孩子不同时存在 ， 反正存在哪个哪个进入队列即可） 。 然后保存当前节点的元素到数组中 。 然后临时队列中的元素 ， 进入真正要进行循环获取层次的队列 ， 队列中始终要保持只有当前层次的节点 。
由于篇幅有限 ， 可能无法很好的把其方式描述清楚 ， 但是看代码会很直观 。
代码实现
【独自快乐|LeetCode | 102.二叉树的层次遍历】C++ 的代码如下：
/** * Definition for a binary tree node. * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:vector> levelOrder(TreeNode* root) {vector> vec;if (root == NULL) {return vec;}// 队列保存树的根节点queue que;que.push(root);while (!que.empty()) {// 保存当前层上节点的值vector v;// 临时队列queue tmp;while (!que.empty()) {TreeNode *p = que.front();que.pop();// 左右节点入队if (p->left) {tmp.push(p->left);}if (p->right) {tmp.push(p->right);}v.push_back(p->val);}// 下一层的节点入队while (!tmp.empty()) {que.push(tmp.front());tmp.pop();}vec.push_back(v);}return vec;}};