二叉树（二）深度遍历和广度遍历

一、层序遍历

广度优先搜索：使用队列，先进先出

模板：

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;}

考虑遇到叶子节点时，就可以返回最小深度了