aboutsummaryrefslogtreecommitdiff
path: root/other/max_product_split_bt.rs
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/max_product_split_bt.rs
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/max_product_split_bt.rs')
-rw-r--r--other/max_product_split_bt.rs43
1 files changed, 43 insertions, 0 deletions
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<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::cell::RefCell;
+use std::rc::Rc;
+const MOD: i64 = 1_000_000_007;
+impl Solution {
+ pub fn max_product(root: Option<Rc<RefCell<TreeNode>>>) -> 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<Rc<RefCell<TreeNode>>>, sums: &mut Vec<i64>) -> 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
+ }
+ }
+}