每日算法题—二叉树的层平均值

题目

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组
来源：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
例如输入:

输出: [1, 2.5, 7.5]

思路

方法1：使用map，递归将每个node的层级和节点值存入map中，最后再遍历map，将map中记录的节点值求个平均即可
方法2：使用队列，逐层遍历，具体逻辑看代码注释

实现

方法1：

    fun averageOfLevels(root: TreeNode?):DoubleArray {
        val resultMap = HashMap<Int, ArrayList<Int>>()//用来记录节点所在层级和该层级的所有节点值
        recursion(root, 0, resultMap)//递归，将树的所有节点的层级和值都记录到map中
        val result = DoubleArray(resultMap.size)
        for ((key, value) in resultMap) {//遍历map，求出每层的平均值
            result[key] = value.average()
        }
        return result
    }

    fun recursion(node: TreeNode?, level: Int, hashMap: HashMap<Int, ArrayList<Int>>) {
        node?.let {
            val l = hashMap[level]
            if (l != null) {
                l.add(it.value)
            } else {
                hashMap[level] = arrayListOf(it.value)
            }
            recursion(it.left, level + 1, hashMap)//孩子节点的层级比当前层级多1层，所以要加1
            recursion(it.right, level + 1, hashMap)
        }
    }

方法2：

fun averageOfLevels(root: TreeNode?):DoubleArray {
        val result = ArrayList<Double>()
        val queue = LinkedList<TreeNode>()
        var node: TreeNode
        var sum: Double
        var levelSize: Int
        root?.let {
            queue.push(it)
            while (!queue.isEmpty()) {
                sum = 0.0//记得每层计算完平均值后要把sum清0
                levelSize = queue.size//此时队列中全部是处于同一个层级的节点，记录下个数，之后依次弹出当前层的所有节点，并将下一层的节点入队
                for (i in 0 until levelSize) {
                    node = queue.poll()
                    sum += node.value
                    node.left?.let { queue.offer(it) }//将同一层的节点入队
                    node.right?.let { queue.offer(it) }//将同一层的节点入队
                }
                result.add(sum / levelSize)
            }
        }
        return result.toDoubleArray()
    }