LeetCode Daily

class Solution {
public:
    void dfs(TreeNode* cur, int level, vector<int>& ans) {
        if(!cur) {
            return;
        }
        if(ans.size() <= level) {
            ans.push_back(0);
        }
        dfs(cur->left, level + 1, ans);
        dfs(cur->right, level + 1, ans);
        ans[level] += cur->val;
    }
    int maxLevelSum(TreeNode* root) {
        vector<int> ans; ans.reserve(15);
        dfs(root, 0, ans);
        return max_element(ans.begin(), ans.end()) - ans.begin() + 1;
    }
};

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn dfs(cur: Option<Rc<RefCell<TreeNode>>>, level: i32, ans: &mut Vec<i32>) {
        if cur.is_none() {
            return;
        }
        if ans.len() <= level as usize {
            ans.push(0);
        }
        let cur = cur.clone().unwrap();
        let lc = cur.borrow().left.clone();
        let rc = cur.borrow().right.clone();
        Solution::dfs(lc, level + 1, ans);
        Solution::dfs(rc, level + 1, ans);
        ans[level as usize] += cur.borrow().val;
    }
    pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut ans = Vec::<i32>::with_capacity(15);
        Solution::dfs(root.clone(), 0, &mut ans);
        let mut mx = (-1, i32::MIN);
        for (idx, val) in ans.iter().enumerate() {
            if mx.1 < *val {
                mx = (idx as i32, *val);
            }
        }
        return mx.0 + 1;
    }
}

class Solution {
public:
    static constexpr int M = 1e9 + 7;
    int dfs(TreeNode* cur, int all_sum, long long& ans) {
        if(!cur) return 0;
        int sum = cur->val + dfs(cur->left, all_sum, ans) + dfs(cur->right, all_sum, ans);
        ans = max(ans, 1ll * sum * (all_sum - sum));
        return sum;
    }
    int maxProduct(TreeNode* root) {
        long long ans = 0;
        int all_sum = dfs(root, 0, ans);
        ans = 0;
        dfs(root, all_sum, ans);
        return ans % M;
    }
};

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn dfs(cur: Option<Rc<RefCell<TreeNode>>>, all_sum: i64) -> (i64, i64) {
        if(cur.is_none()) {
            return (0, 0);
        }
        let lv = Solution::dfs(cur.clone().unwrap().borrow().left.clone(), all_sum);
        let rv = Solution::dfs(cur.clone().unwrap().borrow().right.clone(), all_sum);
        let sum = lv.0 + rv.0 + cur.clone().unwrap().borrow().val as i64;
        let ans = lv.1.max(rv.1).max((all_sum - sum) * sum);
        return (sum, ans);
    }
    pub fn max_product(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        const M: i64 = 1000000007;
        let (all_sum, _) = Solution::dfs(root.clone(), 0_i64);
        (Solution::dfs(root.clone(), all_sum).1 % M) as i32
    }
}