Jan 7

lc-1339: Maximum Product of Splitted Binary Tree

My initial thought is doing a DFS pass through the tree. Things to take note of:
- I will go through the tree and calculate the total sum of the tree.
- Knowing the sum of a subtree, the 2nd subtree will therefore be total sum - subtree sum.
- Record the sum of every subtree.
- Maximise S * (Totalsum-S) for all S (Subtree)
- Then we can know the max sum by combining subtrees.
```
// 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;
impl Solution {
    pub fn max_product(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut all_sum = Vec::new();

        let total_sum: i64 = Self::tree_sum(root, &mut all_sum);
        let mut best: i64 = 0;

        for i in all_sum {
            let i64_val = i as i64;
            best = best.max(i64_val * (total_sum -i64_val));
        }

        let modulo: i64 = 1_000_000_007;
        let ans_i64 = best % modulo;
        ans_i64 as i32
    }

    pub fn tree_sum(node: Option<Rc<RefCell<TreeNode>>>, subtree_arr: &mut Vec<i32>) -> i64 {

        let Some(rc_node) = node else {
            return 0;
        };
        
        let node_ref= rc_node.borrow();

        let left = node_ref.left.clone();
        let right = node_ref.right.clone();
        let s = node_ref.val as i64 + Self::tree_sum(left, subtree_arr) + Self::tree_sum(right, subtree_arr);

        subtree_arr.push(s as i32);

        return s
    }
}
```

Another approach using 2 pass DFS
```
// 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;
impl Solution {
    pub fn max_product(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let total_sum = Self::total_sum(root.clone());
        let mut best: i64 = 0;

        Self::dfs(root.clone(), total_sum, &mut best);

        (best % 1_000_000_007) as i32
    }

    fn total_sum(node: Option<Rc<RefCell<TreeNode>>>) -> i64 {
        let Some(rc_node) = node else {
            return 0;
        };

        let node_ref = rc_node.borrow();

        node_ref.val as i64 + Self::total_sum(node_ref.left.clone()) + Self::total_sum(node_ref.right.clone())
    }

    fn dfs(node: Option<Rc<RefCell<TreeNode>>>, total_sum: i64, best: &mut i64) -> i64 {
        let Some(rc_node) = node else {
            return 0;
        };

        let node_ref = rc_node.borrow();
        let left_dfs = Self::dfs(node_ref.left.clone(), total_sum, best);
        let right_dfs = Self::dfs(node_ref.right.clone(), total_sum, best);

        let sub_sum = node_ref.val as i64 + left_dfs + right_dfs;

        let product = sub_sum * (total_sum - sub_sum);
        *best = (*best).max(product);

        sub_sum
    }
}
```