【刷爆力扣之637. 二叉树的层平均值】

2024-05-02 12:52
文章标签 二叉树 平均值 爆力 637

本文主要是介绍【刷爆力扣之637. 二叉树的层平均值】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

637. 二叉树的层平均值

方法一:深度优先搜索dfs

使用深度优先搜索计算二叉树的层平均值,需要维护两个数组,counts 用于存储二叉树的每一层的节点数,sums 用于存储二叉树的每一层的节点值之和。搜索过程中需要记录当前节点所在层,如果访问到的节点在第 i 层,则将 counts[i] 的值加 1,并将该节点的值加到 sums[i]

遍历结束之后,第 i 层的平均值即为 sums[i]/counts[i]

class Solution {public List<Double> averageOfLevels(TreeNode root) {// 维护两个集合,一个集合counts记录每一层节点个数,一个集合sums记录每一层节点总和List<Integer> counts = new ArrayList<Integer>();List<Double> sums = new ArrayList<Double>();dfs(root, 0, counts, sums);List<Double> averages = new ArrayList<Double>();int size = sums.size();for (int i = 0; i < size; i++) {averages.add(sums.get(i) / counts.get(i));}return averages;}// 深度优先遍历public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {if (root == null) {return;}// 如果当前层小于sums集合的长度,说明之前已经遍历过当前层的其他节点if (level < sums.size()) {sums.set(level, sums.get(level) + root.val);// 求和counts.set(level, counts.get(level) + 1); // 节点数加1} else { // 否则,说明第一次遍历当前层sums.add(1.0 * root.val); // 添加新的一层的元素counts.add(1); // count为1}// 左孩子dfs(root.left, level + 1, counts, sums);// 右孩子dfs(root.right, level + 1, counts, sums);}
}

方法二:广度优先搜索

也可以使用广度优先搜索计算二叉树的层平均值。从根节点开始搜索,每一轮遍历同一层的全部节点,计算该层的节点数以及该层的节点值之和,然后计算该层的平均值。

如何确保每一轮遍历的是同一层的全部节点呢?我们可以借鉴层次遍历的做法,广度优先搜索使用队列存储待访问节点,只要确保在每一轮遍历时,队列中的节点是同一层的全部节点即可。具体做法如下:

  • 初始时,将根节点加入队列;
  • 每一轮遍历时,将队列中的节点全部取出,计算这些节点的数量以及它们的节点值之和,并计算这些节点的平均值,然后将这些节点的全部非空子节点加入队列,重复上述操作直到队列为空,遍历结束。

由于初始时队列中只有根节点,满足队列中的节点是同一层的全部节点,每一轮遍历时都会将队列中的当前层节点全部取出,并将下一层的全部节点加入队列,因此可以确保每一轮遍历的是同一层的全部节点。

具体实现方面,可以在每一轮遍历之前获得队列中的节点数量 size,遍历时只遍历 size个节点,即可满足每一轮遍历的是同一层的全部节点。

public List<Double> averageOfLevels(TreeNode root) {List<Double> result = new ArrayList<>();// 层序遍历需要的队列数据结构Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {Double level = null;// 每一层节点个数int size = queue.size();// 每一层节点的总和Double sum = 0.0;// 每轮循环,将当前层的所有节点全部弹出,将下一层的所有节点全部入队for (int i = 0; i < size; i++) {TreeNode polled = queue.poll();sum += polled.val;TreeNode left = polled.left;TreeNode right = polled.right;if (left != null) {queue.offer(left);}if (right != null) {queue.offer(right);}}result.add(sum / size);}return result;
}

这篇关于【刷爆力扣之637. 二叉树的层平均值】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/954282

相关文章

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

在二叉树中找到两个节点的最近公共祖先(基于Java)

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo

数据结构--二叉树(C语言实现,超详细!!!)

文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念 二叉树(Binary Tree)是数据结构中一种非常重要的树形结构,它的特点是每个节点最多有两个子节点,通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

222.完全二叉树的节点个数

(写给未来遗忘的自己) 题目: 代码: class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s

代码随想录 -- 二叉树 -- 平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode) 思路:仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数:如果传入根节点为空返回真;如果根节点 | 左子树的层数 - 右子树的层数 | 大于1,返回假;最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root

【数据结构】你真的学会了二叉树了吗,来做一做二叉树的算法题及选择题

文章目录 1. 二叉树算法题1.1 单值二叉树1.2 相同的树1.3 另一棵树的子树1.4 二叉树的遍历1.5 二叉树的构建及遍历 2. 二叉树选择题3. 结语 1. 二叉树算法题 1.1 单值二叉树 https://leetcode.cn/problems/univalued-binary-tree/description/ 1.2 相同的树 https://leet

二叉树的层次遍历(10道)

(写给未来遗忘的自己) 102.二叉数的层序遍历(从上到下) 题目: 代码: class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; queue<TreeNode*> node; if (root == nullptr) {

求二叉树的深度——(力扣c语言)

题目如下: 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1: 输入:root = [3,9,20,null,null,15,7]输出:3 示例 2: 输入:root = [1,null,2]输出:2 题目解析: 上题就是要利用递归对目标进行访问找到叶子节点之后记录并返回到根节点之后对左右两个