508. Most Frequent Subtree Sum #

Problem #

Given the root of a tree, you are asked to find the most frequent subtree sum. 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). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1

Input:

  5
 /  \
2   -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2

Input:

  5
 /  \
2   -5

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

Problem Summary #

Given the root of a binary tree, find the subtree sum that appears most frequently. The subtree sum of a node is defined as the sum of all node values in the binary tree rooted at that node (including the node itself). Then find the subtree sum that appears most frequently. If multiple elements appear the same number of times, return all elements that appear most frequently (in any order). Note: Assume that the sum of values in any subtree can be represented by a 32-bit signed integer.

Solution Ideas #

• Given a tree, compute the sum of all node values in the subtree rooted at each node, then output the sum with the highest frequency among these sums. If multiple sums have the highest frequency, output all of them.
• Recursively find the accumulated sum of each node, use a map to record frequencies, and finally output the sums with the highest frequency.

Code #

package leetcode

import (
	"sort"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// Solution 1: maintain the maximum frequency, no sorting needed
func findFrequentTreeSum(root *TreeNode) []int {
	memo := make(map[int]int)
	collectSum(root, memo)
	res := []int{}
	most := 0
	for key, val := range memo {
		if most == val {
			res = append(res, key)
		} else if most < val {
			most = val
			res = []int{key}
		}
	}
	return res
}

func collectSum(root *TreeNode, memo map[int]int) int {
	if root == nil {
		return 0
	}
	sum := root.Val + collectSum(root.Left, memo) + collectSum(root.Right, memo)
	if v, ok := memo[sum]; ok {
		memo[sum] = v + 1
	} else {
		memo[sum] = 1
	}
	return sum
}

// Solution 2: compute all sums and then sort
func findFrequentTreeSum1(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	freMap, freList, reFreMap := map[int]int{}, []int{}, map[int][]int{}
	findTreeSum(root, freMap)
	for k, v := range freMap {
		tmp := reFreMap[v]
		tmp = append(tmp, k)
		reFreMap[v] = tmp
	}
	for k := range reFreMap {
		freList = append(freList, k)
	}
	sort.Ints(freList)
	return reFreMap[freList[len(freList)-1]]
}

func findTreeSum(root *TreeNode, fre map[int]int) int {
	if root == nil {
		return 0
	}
	if root != nil && root.Left == nil && root.Right == nil {
		fre[root.Val]++
		return root.Val
	}
	val := findTreeSum(root.Left, fre) + findTreeSum(root.Right, fre) + root.Val
	fre[val]++
	return val
}