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
Solutions
Solution 1: Hash Table + DFS
We can use a hash table $\textit{cnt}$ to record the frequency of each subtree sum. Then, we use depth-first search (DFS) to traverse the entire tree, calculate the sum of elements for each subtree, and update $\textit{cnt}$.
Finally, we traverse $\textit{cnt}$ to find all subtree sums that appear most frequently.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617181920
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:deffindFrequentTreeSum(self,root:Optional[TreeNode])->List[int]:defdfs(root:Optional[TreeNode])->int:ifrootisNone:return0l,r=dfs(root.left),dfs(root.right)s=l+r+root.valcnt[s]+=1returnscnt=Counter()dfs(root)mx=max(cnt.values())return[kfork,vincnt.items()ifv==mx]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcfindFrequentTreeSum(root*TreeNode)(ans[]int){cnt:=map[int]int{}varmxintvardfsfunc(*TreeNode)intdfs=func(root*TreeNode)int{ifroot==nil{return0}s:=root.Val+dfs(root.Left)+dfs(root.Right)cnt[s]++mx=max(mx,cnt[s])returns}dfs(root)fork,v:=rangecnt{ifv==mx{ans=append(ans,k)}}return}