1二叉树的层平均值
简单
相关标签
相关企业
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
- 树中节点数量在
[1, 104]范围内 -231 <= Node.val <= 231 - 1
思路：
要求计算二叉树每一层节点值的平均值，并将结果存放在一个数组中返回。解题思路是使用队列来实现层次遍历，通过循环遍历每一层节点，计算该层节点值的和并求平均值，然后将平均值存放在结果集中。具体步骤如下：
- 创建一个队列que，用于存放二叉树节点。
- 如果根节点不为空，则将根节点加入队列que中。
- 创建一个vector<double> result，用于存放每一层平均值。
- 循环直到队列que为空：
a. 获取当前层的节点个数，记为size。
b. 创建一个变量sum，用于统计当前层节点值的和。
c. 遍历当前层的每一个节点：- 获取队列que中的第一个节点node。
- 弹出队列que中的第一个节点。
- 将节点值累加到sum中。
- 如果节点的左子节点不为空，则将左子节点加入队列que中。
- 如果节点的右子节点不为空，则将右子节点加入队列que中。
d. 将当前层节点值的平均值(sum / size)存放在结果集result中。
- 返回结果集result。
代码：
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> que; // 创建一个队列用于存放节点
if (root != NULL) que.push(root); // 如果根节点不为空，则将根节点加入队列中
vector<double> result; // 创建一个存放每一层平均值的结果集
while (!que.empty()) { // 循环直到队列为空
int size = que.size(); // 获取当前层的节点个数
double sum = 0; // 统计每一层的和
for (int i = 0; i < size; i++) {
TreeNode* node = que.front(); // 获取队列中的第一个节点
que.pop(); // 弹出队列中的第一个节点
sum += node->val; // 将节点值累加到sum中
if (node->left) que.push(node->left); // 如果左子节点不为空，则加入队列中
if (node->right) que.push(node->right); // 如果右子节点不为空，则加入队列中
}
result.push_back(sum / size); // 将每一层均值放进结果集
}
return result; // 返回结果集
}
};2N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
- 树的高度不会超过
1000 - 树的节点总数在
[0, 10^4]之间
思路：
这道题目是要求对多叉树进行层次遍历，并将每一层节点值存放在一个二维数组中返回。解题思路仍然是使用队列来实现层次遍历，通过循环遍历每一层节点，将节点值存放在对应的向量中，然后将向量存放在结果集中。具体步骤如下：
- 创建一个队列que，用于存放多叉树节点。
- 如果根节点不为空，则将根节点加入队列que中。
- 创建一个vector<vector<int>> result，用于存放每一层节点值的结果集。
- 循环直到队列que为空：
a. 获取当前层的节点个数，记为size。
b. 创建一个向量vec，用于存放当前层节点值。
c. 遍历当前层的每一个节点：- 获取队列que中的第一个节点node。
- 弹出队列que中的第一个节点。
- 将节点值加入向量vec中。
- 遍历节点的子节点，如果子节点不为空则加入队列que中。
d. 将当前层节点值的向量vec存放在结果集result中。
- 返回结果集result。
代码：
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*> que; // 创建一个队列用于存放节点
if(root !=nullptr) que.push(root); // 如果根节点不为空，则将根节点加入队列中
vector<vector<int>> result; // 创建一个存放每一层节点值的结果集
while(!que.empty()){ // 循环直到队列为空
int size = que.size(); // 获取当前层的节点个数
vector<int> vec; // 创建一个向量用于存放当前层节点值
for(int i=0; i<size; i++){
Node* node = que.front(); // 获取队列中的第一个节点
que.pop(); // 弹出队列中的第一个节点
vec.push_back(node->val); // 将节点值加入向量vec中
for(int i=0; i<node->children.size(); i++){
if(node->children[i]) que.push(node->children[i]); // 将子节点加入队列中
}
}
result.push_back(vec); // 将当前层节点值的向量存入结果集中
}
return result; // 返回结果集
}
};3在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：
输入: root = [1,2,3] 输出: [1,3]
提示：
- 二叉树的节点个数的范围是
[0,104] -231 <= Node.val <= 231 - 1
思路：
这道题的重点是通过层次遍历多叉树的节点，记录每一层的最大节点值，并将这些最大节点值存放在一个数组中返回。通过使用队列实现层次遍历，可以有效地处理每一层的节点，并找出最大值。同时，需要注意处理节点为空的情况，避免出现空指针异常。
创建一个队列que，用于存放多叉树节点。
如果根节点不为空，则将根节点加入队列que中。
创建一个vector<vector<int>> result，用于存放每一层节点值的结果集。
循环直到队列que为空：
a. 获取当前层的节点个数，记为size。
b. 初始化当前层的最大值为最小整数值。
c. 遍历当前层的每一个节点：
获取队列que中的第一个节点node。
弹出队列que中的第一个节点。
更新当前层的最大值。
遍历节点的子节点，如果子节点不为空则加入队列que中。
d. 将当前层的最大值存放在结果集result中。
返回结果集result。
代码：
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> que; // 创建一个队列用于存放节点
if(root !=nullptr) que.push(root); // 如果根节点不为空，则将根节点加入队列中
vector<int> result; // 创建一个存放每层最大值的结果集
while(!que.empty()){ // 循环直到队列为空
int size = que.size(); // 获取当前层的节点个数
int maxvalue = INT_MIN; // 初始化最大值为最小整数值
for(int i=0; i<size; i++){
TreeNode* node = que.front(); // 获取队列中的第一个节点
que.pop(); // 弹出队列中的第一个节点
maxvalue = node->val > maxvalue ? node->val : maxvalue; // 更新最大值
if(node->left) que.push(node->left); // 将左子节点加入队列中
if(node->right) que.push(node->right); // 将右子节点加入队列中
}
result.push_back(maxvalue); // 将当前层的最大值存入结果集中
}
return result; // 返回结果集
}
};4电影评分
表：Movies
+---------------+---------+ | Column Name | Type | +---------------+---------+ | movie_id | int | | title | varchar | +---------------+---------+ movie_id 是这个表的主键(具有唯一值的列)。 title 是电影的名字。
表：Users
+---------------+---------+ | Column Name | Type | +---------------+---------+ | user_id | int | | name | varchar | +---------------+---------+ user_id 是表的主键(具有唯一值的列)。
表：MovieRating
+---------------+---------+ | Column Name | Type | +---------------+---------+ | movie_id | int | | user_id | int | | rating | int | | created_at | date | +---------------+---------+ (movie_id, user_id) 是这个表的主键(具有唯一值的列的组合)。 这个表包含用户在其评论中对电影的评分 rating 。 created_at 是用户的点评日期。
请你编写一个解决方案：
- 查找评论电影数量最多的用户名。如果出现平局，返回字典序较小的用户名。
- 查找在
February 2020平均评分最高 的电影名称。如果出现平局，返回字典序较小的电影名称。
字典序 ，即按字母在字典中出现顺序对字符串排序，字典序较小则意味着排序靠前。
返回结果格式如下例所示。
示例 1：
输入： Movies 表： +-------------+--------------+ | movie_id | title | +-------------+--------------+ | 1 | Avengers | | 2 | Frozen 2 | | 3 | Joker | +-------------+--------------+ Users 表： +-------------+--------------+ | user_id | name | +-------------+--------------+ | 1 | Daniel | | 2 | Monica | | 3 | Maria | | 4 | James | +-------------+--------------+ MovieRating 表： +-------------+--------------+--------------+-------------+ | movie_id | user_id | rating | created_at | +-------------+--------------+--------------+-------------+ | 1 | 1 | 3 | 2020-01-12 | | 1 | 2 | 4 | 2020-02-11 | | 1 | 3 | 2 | 2020-02-12 | | 1 | 4 | 1 | 2020-01-01 | | 2 | 1 | 5 | 2020-02-17 | | 2 | 2 | 2 | 2020-02-01 | | 2 | 3 | 2 | 2020-03-01 | | 3 | 1 | 3 | 2020-02-22 | | 3 | 2 | 4 | 2020-02-25 | +-------------+--------------+--------------+-------------+ 输出： Result 表： +--------------+ | results | +--------------+ | Daniel | | Frozen 2 | +--------------+ 解释： Daniel 和 Monica 都点评了 3 部电影（"Avengers", "Frozen 2" 和 "Joker"） 但是 Daniel 字典序比较小。 Frozen 2 和 Joker 在 2 月的评分都是 3.5，但是 Frozen 2 的字典序比较小。
思路：
这个SQL查询的解题思路如下：
1. 首先针对MovieRating表和Users表进行连接查询，通过用户ID将评分记录和用户信息进行关联。
2. 对结果按照用户ID进行分组，然后按照每个用户对电影的评分次数进行降序排列，同时如果评分次数相同的情况下按照用户名称进行升序排列，这样就可以找到评分次数最多的用户。
3. 使用limit 0,1来限制结果集只返回第一条结果，即评分次数最多的用户。
4. 然后使用union all操作符将上述结果与下面的查询结果进行合并。
5. 对MovieRating表和Movies表进行连接查询，通过电影ID将评分记录和电影信息进行关联。
6. 在where子句中筛选出2020年2月份产生的评分记录。
7. 对结果按照电影ID进行分组，然后按照每部电影的评分平均值进行降序排列，同时如果平均值相同的情况下按照电影标题进行升序排列，这样就可以找到2020年2月份评分平均值最高的电影。
8. 使用limit 0,1来限制结果集只返回第一条结果，即评分平均值最高的电影。
代码：
```sql
-- 获取评分次数最多的用户
(
select u.name as 结果 -- 选择用户的名称作为结果列
from MovieRating r join Users u -- 从MovieRating表和Users表中连接查询
on r.user_id=u.user_id -- 根据用户ID进行连接
group by r.user_id -- 按用户ID分组
order by count(r.movie_id) desc, u.name -- 根据电影ID的计数降序排列，若计数相同则按用户名称升序排列
limit 0,1 -- 只取第一条结果
)
union all
-- 获取2020年2月份评分平均值最高的电影
(
select m.title as 结果 -- 选择电影的标题作为结果列
from MovieRating r join Movies m -- 从MovieRating表和Movies表中连接查询
on r.movie_id=m.movie_id -- 根据电影ID进行连接
where r.created_at between '2020-02-01' and '2020-02-29' -- 选择创建日期在2020年2月份的评分记录
group by r.movie_id -- 按电影ID分组
order by avg(r.rating) desc, m.title -- 根据评分的平均值降序排列，若平均值相同则按电影标题升序排列
limit 0,1 -- 只取第一条结果
);
```
