[leetcode] 637. Average of Levels in Binary Tree

DFS

class Solution {
    fun averageOfLevels(root: TreeNode?): DoubleArray {
        val sums = mutableListOf<Double>()
        val nums = mutableListOf<Int>()
        
        averageOfLevels(root, sums, nums, 0)
        
        for (i in sums.indices) {
            sums[i] = sums[i] / nums[i]
        }
        
        return sums.toDoubleArray()
    }
    
    fun averageOfLevels(root: TreeNode?, sums: MutableList<Double>, nums: MutableList<Int>, depth: Int) {
        if (root == null) return
        
        if (sums.size == depth) {
            sums.add(root.`val`.toDouble())
            nums.add(1)
        } else {
            sums[depth] = sums[depth] + root.`val`
            nums[depth] = nums[depth] + 1
        }
        
        averageOfLevels(root.left, sums, nums, depth + 1)
        averageOfLevels(root.right, sums, nums, depth + 1)
    }
}

BFS

class Solution {
    fun averageOfLevels(root: TreeNode?): List<Double> {
        val queue: Queue<TreeNode> = LinkedList()
        queue.add(root!!) // number of nodes >= 1
        val result = mutableListOf<Double>()
        
        while (queue.isNotEmpty()) {
            val n = queue.size
            
            var sum = 0.0
            for (i in 0 until n) {
                val node = queue.poll()
                sum += node.`val`.toDouble()
                
                if (node.left != null) queue.add(node.left)
                if (node.right != null) queue.add(node.right)                
            }
            result.add(sum / n)
        }
        return result
    }
}