二叉树（二）深度遍历和广度遍历
一、层序遍历
广度优先搜索：使用队列，先进先出
模板：
1、定义返回的result和用于辅助的队列
2、队列初始化：
root非空时进队
3、遍历整个队列：大循环while(!que.empty())
记录每层的size以及装每层结果的变量（记得每层循环结束后保存结果的值）
4、遍历每层：小循环for或while(size--)
出1进2：先记录当前即将出队的node
node出队，如果孩子节点非空即进队
vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;//借助队列来实现queue<TreeNode*>que;//（先进先出，层序遍历）（保存节点指针，孩子信息才不丢失）if(root) //先弹进rootque.push(root);while(!que.empty()){//队列不为空时，都要遍历；没有继续加入的，则说明快要遍历完了int size=que.size(); //保存当前层的大小vector<int> vec;//vec记录每层的节点元素，在循环内定义，不用每次清空//将总遍历切割成一层一层的while(size--){//对一层元素进行操作：出一个根节点（要先记录val），则进两个它的孩子节点（如果有）TreeNode*node=que.front();vec.push_back(node->val);que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);}result.push_back(vec);}return result;}变式：求层平均值
vector<double> averageOfLevels(TreeNode* root) {vector<double> result;queue<TreeNode*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size=que.size();//当前层元素个数double sum=0;for(int i=0;i<size;i++){TreeNode* node=que.front(); //先保存sum+=node->val;que.pop();//再弹出if(node->left)//最后进两个que.push(node->left);if(node->right)que.push(node->right);}result.push_back(sum/size);}return result;}注意：最后要用到sum/size；所以不能用while(size--)，因为size会改变，而要用for循环
同理，每层循环要记录size，就是因为que.size()也会改变
二、深度遍历（前中后序，递归）
深度优先搜索：使用栈，先进后出
模板：
前序：
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val); // 根traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右}中序：
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左vec.push_back(cur->val); // 根traversal(cur->right, vec); // 右
}后序：
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右vec.push_back(cur->val); // 根
}三、对比
1、获取最大深度
深度优先（前序）：
int getdepth(TreeNode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left); // 左int rightdepth = getdepth(node->right); // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}广度优先：
int maxDepth(TreeNode* root) {//1、定义结果变量和辅助队列int depth=0;queue<TreeNode*> que;//2、队列初始化if(root)que.push(root);//3、大循环并记录每层的sizewhile(!que.empty()){int size=que.size();//4、小循环：遍历一层，存1出1进2while(size--){TreeNode*node=que.front();que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);}depth++;}return depth;}2、获取最小深度
深度优先（前序）：
int minDepth(TreeNode* root) {if(root==NULL)return 0;int lh=minDepth(root->left);int rh=minDepth(root->right);if(!root->left&&root->right)return 1+rh;if(root->left&&!root->right)return 1+lh;return 1+min(lh,rh);}考虑仅有一个孩子节点时，返回的应是1+子树的最小深度
广度优先：
int minDepth(TreeNode* root) {//1、定义结果变量和辅助队列int depth=0;queue<TreeNode*> que;//2、队列初始化if(root)que.push(root);//3、大循环并记录每层的sizewhile(!que.empty()){int size=que.size();//4、小循环：遍历一层，存1出1进2while(size--){TreeNode*node=que.front();que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);//如果遇到叶子节点了，说明可以完成最小深度计算了if(!node->left&&!node->right)return depth+1;//注意是+1（逻辑上要遍历完一层才+1，这里提前结束就提前加）}depth++;}return depth;}考虑遇到叶子节点时，就可以返回最小深度了