From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/max_product_split_bt.rs | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 other/max_product_split_bt.rs (limited to 'other/max_product_split_bt.rs') diff --git a/other/max_product_split_bt.rs b/other/max_product_split_bt.rs new file mode 100644 index 0000000..6aec321 --- /dev/null +++ b/other/max_product_split_bt.rs @@ -0,0 +1,43 @@ +#[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 + } + } +} -- cgit v1.2.3