題目

給定一個(gè)非空二叉樹, 返回一個(gè)由每層節(jié)點(diǎn)平均值組成的數(shù)組
來(lái)源：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
例如輸入:

輸出: [1, 2.5, 7.5]

思路

方法1：使用map，遞歸將每個(gè)node的層級(jí)和節(jié)點(diǎn)值存入map中，最后再遍歷map，將map中記錄的節(jié)點(diǎn)值求個(gè)平均即可
方法2：使用隊(duì)列，逐層遍歷，具體邏輯看代碼注釋

實(shí)現(xiàn)

方法1：

    fun averageOfLevels(root: TreeNode?):DoubleArray {
        val resultMap = HashMap<Int, ArrayList<Int>>()//用來(lái)記錄節(jié)點(diǎn)所在層級(jí)和該層級(jí)的所有節(jié)點(diǎn)值
        recursion(root, 0, resultMap)//遞歸，將樹的所有節(jié)點(diǎn)的層級(jí)和值都記錄到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)//孩子節(jié)點(diǎn)的層級(jí)比當(dāng)前層級(jí)多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//記得每層計(jì)算完平均值后要把sum清0
                levelSize = queue.size//此時(shí)隊(duì)列中全部是處于同一個(gè)層級(jí)的節(jié)點(diǎn)，記錄下個(gè)數(shù)，之后依次彈出當(dāng)前層的所有節(jié)點(diǎn)，并將下一層的節(jié)點(diǎn)入隊(duì)
                for (i in 0 until levelSize) {
                    node = queue.poll()
                    sum += node.value
                    node.left?.let { queue.offer(it) }//將同一層的節(jié)點(diǎn)入隊(duì)
                    node.right?.let { queue.offer(it) }//將同一層的節(jié)點(diǎn)入隊(duì)
                }
                result.add(sum / levelSize)
            }
        }
        return result.toDoubleArray()
    }