前言
今日文案：
坚持，任何的限制，都是从自己的内心开始的、只有一条路不能选择――那就是放弃的路；只有一条路不能拒绝――那就是成长的路。
一、层序遍历
关键词，广度搜索，一层一层遍历，一下是模板，修改之后，爆肝十题。
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; //建立队列 if (root != NULL) que.push(root); //插入根 vector<vector<int>> result; //结果集 while (!que.empty()) { int size = que.size(); //一定要自定义，因为队列是一直变化的 vector<int> vec； for (int i = 0; i < size; i++) { TreeNode* node = que.front(); //一层一层遍历 que.pop(); //弹出第一个操作 vec.push_back(node->val); //按照中左右，前序遍历 if (node->left) que.push(node->left); if (node->right) que.push(node->right); } result.push_back(vec); //出来一次就是一层的答案 } return result; } };
二、层序遍历||
题目要求：
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
相对于模板只是反转了一下
class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> ans; queue<TreeNode*> que; if(root!=0) { que.push(root); } while(!que.empty()) { int size=que.size(); vector<int>temp; for(int i=0;i<size;i++){ TreeNode*node=que.front(); que.pop(); temp.push_back(node->val); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } ans.push_back(temp); } reverse(ans.begin(),ans.end()); //关键点 return ans; } };
三、二叉树的右视图
相对于模板，我们就是输出结果集最右边的那个元素就行。
class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ans; int count=0; queue<TreeNode*> que; if(root!=0) { que.push(root); } while(!que.empty()) { vector<int> temp; int size=que.size(); for(int i=0;i<size;i++) { TreeNode*node=que.front(); que.pop(); temp.push_back(node->val); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } int a=temp.size(); ans.push_back(temp[a-1]); //重点 } return ans; } };
四、二叉树的层平均值
题目来源：
重点：就是每一层求出之后，然后就计算平均值保存。
class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double> ans; queue<TreeNode*> que; if(root!=0) { que.push(root); } while(!que.empty()) { int size=que.size(); vector<double> temp; for(int i=0;i<size;i++) { TreeNode*node=que.front(); que.pop(); temp.push_back(node->val); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } double sum=0; for(int i=0;i<temp.size();i++) { sum+=temp[i]; } double r=sum/temp.size(); ans.push_back(r); } return ans; } };
五、N叉树的层序遍历
题目来源：
重点：层序遍历二叉树是分别传入父亲的所有的子孩子，只不过二叉树是传入左右孩子，二N叉树不只是左右孩子，但只要把全部孩子传进去就行。
class Solution { public: int maxDepth(Node* root) { if(root==0) return 0; int res=0; for(auto &x:root->children) { int D=maxDepth(x); //寻找深度 res=max(D,res); //最大值就是最大深度 } return res+1; //返回上一层+1 } };
接下来就不一一水了，就是明白一层一层遍历的规律，修改一下找到我们需要的部分就行。
六、翻转二叉树
题目描述
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
题目来源：
思路分析：
我们只需要交换根节点对于左右孩子的指针就行，有点像中序遍历，先改变中节点的值，再向左，交换再下一步，注意一定要是中序遍历，因为这样才能保证每个节点都被交换了。
class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==0) return root; swap(root->left,root->right); invertTree(root->left); invertTree(root->right); return root; } };
七、对称二叉树
题目来源：
思路：
主要是要从外层 里层遍历，然后从值和结构方面判断是否对称。
class Solution { public: bool compare(TreeNode*left,TreeNode*right) { if(left==0&&right!=0) //判断结构是否对称 { return false; } if(left!=0&&right==0) { return false; } if(left==0&&right==0) //结构对称了就返回真 return true; if(left->val!=right->val) //判断值是否相等，一定要在后面否则会操控空指针 { return false; } bool outside=compare(left->left,right->right); //里外层遍历 bool inside=compare(left->right,right->left); return outside&&inside; } bool isSymmetric(TreeNode* root) { if(root==0) { return true; } return compare(root->left,root->right); } };
总结
层序遍历模板要熟，用deque模板，反转二叉树是中序控制翻转，对称二叉树则要明白遍历对称顺序，一定要明白里外一起遍历，从结构和值来判断。
