LeetCode in Kotlin

508. Most Frequent Subtree Sum

Medium

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Example 1:

Input: root = [5,2,-3]

Output: [2,-3,4]

Example 2:

Input: root = [5,2,-5]

Output: [2]

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

Solution

import com_github_leetcode.TreeNode

/*
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    private val cache = mutableMapOf<Int, Int>()

    fun findFrequentTreeSum(root: TreeNode?): IntArray {
        treeSum(root)
        if (cache.isEmpty()) {
            return IntArray(0)
        }
        val max = cache.maxBy { it.value }.value
        return cache.filter { it.value == max }.map { it.key }.toIntArray()
    }

    private fun treeSum(node: TreeNode?): Int {
        return if (node == null) {
            0
        } else {
            val sum = node.`val` + treeSum(node.left) + treeSum(node.right)
            cache[sum] = cache.getOrDefault(sum, 0) + 1
            sum
        }
    }
}

This site is open source. Improve this page.