aboutsummaryrefslogtreecommitdiff
path: root/max_product_split_bt.rs
diff options
context:
space:
mode:
Diffstat (limited to 'max_product_split_bt.rs')
-rw-r--r--max_product_split_bt.rs43
1 files changed, 0 insertions, 43 deletions
diff --git a/max_product_split_bt.rs b/max_product_split_bt.rs
deleted file mode 100644
index 6aec321..0000000
--- a/max_product_split_bt.rs
+++ /dev/null
@@ -1,43 +0,0 @@
-#[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
- }
- }
-}