37.哀家要长脑子了！--层序遍历

gongmi层序遍历模板

vector<vector<int>> levelOrder(TreeNode *root){queue<TreeNode*> que;vector<vector<int>> res;if(root != nullptr)que.push(root);while(!que.empty()){int size = que.size();vector<int> storey;for(int i = 0; i < size; i++){TreeNode *node = que.front();que.pop();storey.push_back(node->val);if(node->left)  que.push(node->left);if(node->right)  que.push(node->right);}res.push_back(storey);}return res;
}

这个模板可以打十个👊

用一个临时数字storey保存每一层的结点，用一个结果数组res保存总共的层，也就是最终的结果了。用队列que对每层的结点进行操作

大白话解说：当根节点不是空结点的时候，就把它放入队列中；当队列不为空的时候，有以下操作：新创一个数组storey，获取队列的大小，在队列大小中循环以下操作：（砖心砖心！！）获取队头结点node，将队头结点出队，将node的值放入数组storey中，然后把node的左右孩子先后加入队列中，结束队列循环的大小后就把所新建的数组storey放到返回的结果数组中。

可以想象成，这个数组stroey存储每一层的结点，这个队列呢就是用来获取每一层的结点以及这个结点的左右孩子。所以队列的大小就是每一层结点个数的多少。然后我们要对每一层的结点都进行这样的操作：取结点，出队，把它的元素存入，它的左右孩子也进入队列中等待操作。

1.102. 二叉树的层序遍历 - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;queue<TreeNode*> q;if(root != nullptr) q.push(root);while(!q.empty()){vector<int> tmp;int size = q.size();for(int i = 0; i < size; i++){TreeNode* node = q.front();q.pop();tmp.push_back(node->val);if(node->left) q.push(node->left);if(node->right) q.push(node->right);}res.push_back(tmp);}return res;}
};

 2.107. 二叉树的层序遍历 II - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;queue<TreeNode*> que;if(root != nullptr)que.push(root);while(!que.empty()){vector<int> vec;int size = que.size();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);}res.push_back(vec);}reverse(res.begin(), res.end());return res;}
};

 3.199. 二叉树的右视图 - 力扣（LeetCode）

  这个挺有意思的，可能是因为我脑子缺根筋，只会走直线吧。。。。

 右视图就是只能看到最右边的也就是每层的最后一个结点，那么我们就只要把最后一个结点给存入数组就好（i == size)，而不是每一个。

错误思路：我本来想只将右结点进入队列，这是不对的，还是会把这个结点的不能看到得到左结点给存入结果数组，没有清楚题目的意思。我又想在这个基础上结点的右结点为空左结点不为空时才把这个结点入队。呃呃。不知道自己的脑子用什么做的。。。。。。。

本质！本质！！抓事情的本质！！！

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;vector<int> res;if(root != nullptr)que.push(root);while(!que.empty()){int size = que.size();for(int i = 0; i < size; i++){TreeNode *node = que.front();que.pop();if(i == size - 1) res.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}    }return res;}
};

3.637. 二叉树的层平均值 - 力扣（LeetCode）

就在每一层操作，也就是每一次的队列。

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;queue<TreeNode*> que;if(root != nullptr) que.push(root);while(!que.empty()){double ave = 0;int size = que.size();for(int i = 0;  i < size; i++){TreeNode* node = que.front();que.pop();ave += node->val;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}ave /= size;res.push_back(ave);}return res;}
};

4.429. N 叉树的层序遍历 - 力扣（LeetCode）

 

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> res;queue<Node*> que;if(root != nullptr)que.push(root);while(!que.empty()){int size = que.size();vector<int> tmp;for(int i = 0; i < size; i++){Node*node = que.front();que.pop();tmp.push_back(node->val);int count = node->children[i].size();for(int j = 0; j < count; j++){if(node->children[j]) que.push(node->children[j]);}}res.push_back(tmp);}        return res;}
};

要弄清楚数据结构，每个结点有两部分，一个是结点的元素值val，一个是Node结点数组children，children里面存储的也就是该结点的孩子，我们要遍历每个结点的孩子，就要把这么多的孩子在操作这个结点的时候，把孩子们入队

5.515. 在每个树行中找最大值 - 力扣（LeetCode）

 就在每一层也就是每一次新队列的时候记录一下最大的呗

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

6.116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

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

7.104. 二叉树的最大深度 - 力扣（LeetCode）

​

class Solution {
public:int maxDepth(TreeNode* root) {int res = 0;queue<TreeNode*> que;if(root != nullptr)que.push(root);while(!que.empty()){int size = que.size();res++;for(int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return res;}
};

 要不就在每一层的时候记录一下深度，要不就套用层序遍历的模板然后返回它的结果数组大小

 8.111. 二叉树的最小深度 - 力扣（LeetCode）

class Solution {
public:int minDepth(TreeNode* root) {int res = 0;queue<TreeNode*> que;if(root != nullptr)que.push(root);while(!que.empty()){int size = que.size();res++;for(int i = 0; i < size; i++){TreeNode *node = que.front();que.pop();if(!(node->left) && !(node->right)) return res;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return res;}
};

 遇到左右孩子都是空结点的立刻返回！！

9.226. 翻转二叉树 - 力扣（LeetCode）​

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr)return NULL;swap(root->left, root->right);invertTree(root->left);invertTree(root->right);return root;}
};

 要按照先序遍历或者后序遍历，如果是中序遍历的话，下一个也要是继续反转左子树而不是右子树，因为这样的话，顺序才不会乱。

10.101. 对称二叉树 - 力扣（LeetCode）

​​

class Solution {
public:bool compare(TreeNode *left, TreeNode *right){if(left != nullptr && right == nullptr) return false;else if(left == nullptr && right != nullptr) return false;else if(left == nullptr && right == nullptr) return true;else if(left->val != right->val) return true;bool out = compare(left->left, right->right);bool inner = compare(left->right, right->left);bool isSame = out && inner;return isSame;}bool isSymmetric(TreeNode* root) {if(root == nullptr)return NULL;return compare(root->left, root->right);}
};

 这题还挺有意思的，但我是真的还没有跟递归产生共鸣。。。。

左边为空右边不为空，不对称；左边不为空右边为空，不对称；左右都为空，对称；排除存在空结点的情况后，左右的值不相等，不对称；这两个结点对称后，它俩的孩子结点也要对称，于是就递归调用这个方法，比较外侧的两个结点和内侧的两个结点。