提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

二叉树的分类

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。

二叉搜索树：有数值的二叉树，是一个有序树。若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的遍历

1.递归法

2. 迭代法

**3. 层序遍历

leetcode102、107题：打印层序（层序的逆序）

class Solutions{
public:vector<vector<int>> levelOrder(TreeNode*root){vector<vector<int>> result;//存储结果queue<TreeNode*> que;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();vector<int> vec;for(int i=0;i<size;i++){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);}//reverse(result.begin(),result.end()); //107题return result;}
};

leetcode199题：右视图

class Solution{
public:vector<int> rightSideView(TreeNode* root){vector<int> result;//存储结果queue<TreeNode*> que;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();for(int i=0;i<size;i++){TreeNode*node = que.front();if(i == size-1) result.push_back(node->val);//打印每一行末尾索引的元素que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;}
};

leetcode637题：返回每一层均值

class Solution{
public:vector<int> rightSideView(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;}
};

leetcode429题：返回每一层所有包括children

class Solution{
public:vector<vector<int>> levelOrder(Node* root){vector<vector<int>> result;//存储结果queue<Node*> que;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();vector<int> vec;for(int i=0;i<size;i++){Node *node = que.front();vec.push_back(node->val);que.pop();for(int i = 0;i<node->children.size();i++){if(node->children[i]) que.push(node->children[i]);}}     result.push_back(vec);}return result;}
};

leetcode515题：返回每一层的max

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> result;queue<TreeNode*> que;if (root != NULL) que.push(root);while(!que.empty()){int size = que.size();vector<int> vec;int max_val = INT_MIN;for(int i= 0;i<size;i++){TreeNode*node = que.front();vec.push_back(node->val);que.pop();max_val = node->val>max_val ? node->val :max_val;if(node->right) que.push(node->right);if(node->left)  que.push(node->left);}result.push_back(max_val);}return result;}
};

leetcode116（117完全一样）题：返回每一层的最右

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size = que.size();for(int i = 0;i<size;i++){Node *cur = que.front();que.pop();if(i==size-1) cur->next = NULL;else cur->next = que.front();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);         }}
return root;

leetcode104 题：返回最大深度（就是层数）

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size = que.size();for(int i = 0;i<size;i++){Node *cur = que.front();que.pop();if(i==size-1) cur->next = NULL;else cur->next = que.front();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);         }}
return root;

总结

总的来说就是套模板，把102题的最基础的层序模板记住，其余稍加改动即可。
参考：代码随想录https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html