#[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option>>, pub right: Option>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } use std::cell::RefCell; use std::rc::Rc; const MOD: i64 = 1_000_000_007; impl Solution { pub fn max_product(root: Option>>) -> i32 { let mut sums = Vec::new(); Self::dfs(&root, &mut sums); ((0..sums.len() - 1) .map(|i| sums[i] * (sums[sums.len() - 1] - sums[i])) .max() .unwrap() % MOD) as i32 } fn dfs(node: &Option>>, sums: &mut Vec) -> i64 { if let Some(n) = node { let sum = n.borrow().val as i64 + Self::dfs(&n.borrow().left, sums) + Self::dfs(&n.borrow().right, sums); sums.push(sum); sum } else { 0 } } }