my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

LeetCode(6)-二叉树的层平均值

王伟2020年9月12日158人围观
简介LeetCode(6)-二叉树的层平均值

二叉树的层平均值

在经历了LeetCode每日各种组合的狂轰洗礼下,人们似乎都爱上了组合!

但今天这道二叉树的层平均值也是组合之前的一道非常相似的题。

LeetCode(4)-二叉树的层次遍历

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组

 

示例 1

输入
    3
   / \
  9  20
    /  \
   15   7
输出[3, 14.5, 11]
解释
 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 因此返回 [3, 14.5, 11] 

题解:

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

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

3.初始时,将根节点加入队列;

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

 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// BFS解法
var averageOfLevels = function(root) {
    if(root==null) return []
    const queue = [] // 创建队列
    const res = []
    queue.push(root)
    while(queue.length){
        let levelSize = queue.length
        let levelSum = 0
        for(let i = 0;i<levelSize;i++){ // 遍历每层的node节点
            let cur = queue.shift() 
            levelSum += cur.val
            if(cur.left){
                queue.push(cur.left)
            }
            if(cur.right){
                queue.push(cur.right)
            }
        }
        res.push(levelSum/levelSize)
    }
    return res
};

同理也可以使用DFS遍历

题解

1.记录当前处理的层数

2.遇到相同层数的节点累加到同层中,统计累计个数+1

3.最终按层计算平均值

var averageOfLevels = function(root) {
    if(root==null) return []  
    const res = []
    const map = new Map()
    const dfs = function(root,level){
        if(root == null) return 
        map.set(level,(map.get(level)||0)+1) //map记录层数
        res[level] = (res[level]||0)+root.val //res记录层数的和
        dfs(root.left,level+1)
        dfs(root.right,level+1)
    }
    dfs(root,0)
    for(let i = 0;i<res.length;i++){
        res[i] = res[i]/map.get(i)
    }
    return res
};

路漫漫其修远兮,吾将上下而求索


文章评论

来说句话吧.... 共有评论数:0条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话