二叉树的层序遍历

广度优先搜索

我们可以用一种巧妙的方法修改广度优先搜索：

首先根元素入队
当队列不为空的时候

1.求当前队列的长度 Si
2.依次从队列中取 Si 个元素进行拓展，然后进入下一次迭代

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) { //初始化队列同时将第一层节点加入队列中，即根节点queue<TreeNode*> az;vector<vector<int>> sz;if(root==nullptr){return sz;}az.push(root);//外层的while循环迭代的是层数while(!az.empty()){//记录当前队列大小int size=az.size();vector<int> a;//遍历这一层的所有节点for(int i=0;i<size;i++){ //从队首取出元素TreeNode* node=az.front();az.pop();a.push_back(node->val);if(node->left) az.push(node->left);if(node->right)az.push(node->right);}sz.push_back(a);}return sz;}
};

大家请记住这个模板,后面的几个练习题，都是在这个上面稍作更改.

二叉树的层序遍历II

相对于上面的题目，我们就需要把数组翻转一下就好了.

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> az;queue<TreeNode*> sz;if(root==nullptr){return az;}sz.push(root);while(!sz.empty()){vector<int> a;int size=sz.size();for(int i=0;i<size;i++){TreeNode* node=sz.front();sz.pop();a.push_back(node->val);if(node->left) sz.push(node->left);if(node->right) sz.push(node->right);}az.push_back(a);}reverse(az.begin(),az.end());return az;}
};

二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

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

二叉树的层平均值

本题就是层序遍历的时候把一层求个总和在取一个均值。

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

N叉树的层序遍历

这题就是跟第一题基本一样的，只不过节点多了几个孩子

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> az;queue<Node*> sz;if(root==nullptr){return az;}sz.push(root);while(!sz.empty()){vector<int> a;int size=sz.size();for(int i=0;i<size;i++){Node* node=sz.front();sz.pop();a.push_back(node->val);for(int i=0;i<node->children.size();i++){if(node->children[i])sz.push(node->children[i]);}}az.push_back(a);}return az;}
};

在每个树行中找最大值

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

填充每个节点的下一个右侧节点指针

回想一下二叉树的层次遍历，用广度优先实现的时候，就是层层遍历，每层临时遍历的节点都会放到一个队列中。队列中保存了第 i 层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。

class Solution {public Node connect(Node root) {if (root == null) {return root;}// 初始化队列同时将第一层节点加入队列中，即根节点Queue<Node> queue = new LinkedList<Node>(); queue.add(root);// 外层的 while 循环迭代的是层数while (!queue.isEmpty()) {// 记录当前队列大小int size = queue.size();// 遍历这一层的所有节点for (int i = 0; i < size; i++) {// 从队首取出元素Node node = queue.poll();// 连接if (i < size - 1) {node.next = queue.peek();}// 拓展下一层节点if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}}// 返回根节点return root;}
}

填充每个节点的下一个右侧节点指针II

和上题是完全一样的

class Solution {
public:Node* connect(Node* root) {if (root == nullptr) {return root;}// 初始化队列同时将第一层节点加入队列中，即根节点queue<Node*> Q;Q.push(root);// 外层的 while 循环迭代的是层数while (!Q.empty()) {// 记录当前队列大小int size = Q.size();// 遍历这一层的所有节点for(int i = 0; i < size; i++) {// 从队首取出元素Node* node = Q.front();Q.pop();// 连接if (i < size - 1) {node->next = Q.front();}// 拓展下一层节点if (node->left != nullptr) {Q.push(node->left);}if (node->right != nullptr) {Q.push(node->right);}}}// 返回根节点return root;}
};

二叉树的最大深度

这题前面有讲过，可以参考这篇博客:力扣刷题之二叉树的最大深度_skeet follower的博客-CSDN博客

二叉树的最小深度

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

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