Most frequent subtree sum

Hash Table Tree Depth-First Search Binary Tree

69.0% acceptance

Feb 19, 2026

2369

333

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).

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
  pub fn find_frequent_tree_sum(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut freq: HashMap<i32, i32> = HashMap::new();
    Self::dfs(&root, &mut freq);
    let max_freq = freq.values().cloned().max().unwrap_or(0);
    freq.into_iter()
      .filter(|&(_, v)| v == max_freq)
      .map(|(k, _)| k)
      .collect()
  }
  
  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, freq: &mut HashMap<i32, i32>) -> i32 {
    if let Some(n) = node {
      let nb = n.borrow();
      let left = Self::dfs(&nb.left, freq);
      let right = Self::dfs(&nb.right, freq);
      let sum = nb.val + left + right;
      *freq.entry(sum).or_insert(0) += 1;
      sum
    } else {
      0
    }
  }
}