508.most-frequent-subtree-sum.md

508. Most Frequent Subtree Sum

Postorder

1. Calculate the sum of subtree 1.1 Postorder to get the sum of children 1.2 Sum the root value itself
2. Accumulate the frequency of sum
3. Update the maximum frequency
4. Scan the frequency map to get the most frequent sum

private val sumFrequency = HashMap<Int, Int>()
private var maxFrequency = 0

fun findFrequentTreeSum(root: TreeNode?): IntArray {
    sum(root)
    val results = mutableListOf<Int>()
    for ((sum, freq) in sumFrequency) {
        if (freq == maxFrequency) results.add(sum)
    }
    return results.toIntArray()
}

private fun sum(root: TreeNode?): Int {
    if (root == null) return 0
    val currentSum = root.`val` + sum(root.left) + sum(root.right)
    val currentFrequency = (sumFrequency[currentSum] ?: 0) + 1
    sumFrequency[currentSum] = currentFrequency
    maxFrequency = maxOf(maxFrequency, currentFrequency)

    return currentSum
}

• Time Complexity: O(n).
• Space Complexity: O(n) for the frequency map and recursion stack. There are n nodes in the tree, so there are n possible different sums.