【LeetCode102】逐层输出二叉树（层次遍历）

1.题目

2.思路

层次遍历：借助队列，先将根结点入队，然后循环出队首结点，并且将该结点的左子树和右子树加入队列中。

（1）题目要求输出每层的结点，而常规模板中的队列是各层结点混在一起的，所以为了区分每层，在原本模板的while里面加了个for循环——该for循环即将一层的结点存入layer数组中，之所以for的遍历次数即改层的结点个数width确定，是因为在进入for前的队列长度即为该层的结点个数。

（2）队列中存放的是node*型，而非node型——否则当需要修改队首元素时，就无法对原元素进行修改（只是修改了队列中的副本）；当然如果是使用静态二叉链表存树的写法，队列就是queue<int>q了。

（3）由于可能一开始为空树，所以需要判空，即若为空则返回二维数组ans，注意看清返回值，而非返回NULL;

（4）要非常熟练树的模板。

3.代码

/*** 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<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*>q;//放指针vector<vector<int>>ans;if(!root)return ans;q.push(root);while(!q.empty()){//如果队列不空vector<int>layer;layer.clear();int width=q.size();for(int i=0;i<width;i++){//把一层的结点存入layer数组中,关键！TreeNode* temp=q.front();q.pop();layer.push_back(temp->val);if(temp->left){q.push(temp->left);}if(temp->right){q.push(temp->right);}}ans.push_back(layer);//一层完毕}return ans;}
};

在《剑指offer》中的32-I 从上到下打印二叉树，做法和这题是一样的，虽然不需要二维数组，只用一维数组，即不用多个layer数组：

/*** 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<int> levelOrder(TreeNode* root) {queue<TreeNode*>q;vector<int>ans;if(!root) return ans;q.push(root);while(!q.empty()){int width = q.size();for(int i = 0; i < width; i++){TreeNode* temp = q.front();q.pop();ans.push_back(temp->val);if(temp->left){q.push(temp->left);} if(temp->right){q.push(temp->right);}}}return ans;}
};