Jan 6

LC-1161: Maximum Level Sum of a Binary Tree (Rust)

This is a classic tree transversal problem. The type of tree is not significant here. My go to is a level order (breadth first) transversal, either recursively or iteratively.
- Calculate sum
- Compare the sum and return the max
- If 2 levels have the same max sum, return the smallest level number
- The max sum itself can be negative
- Initialize max_sum at neg infinity

```
// 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_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut level_sums = Vec::new();

        Self::level_order_rec(&root, 0, &mut level_sums);

        let mut max_sum = i32::MIN;
        let mut max_level = 1;

        for (idx, &sum) in level_sums.iter().enumerate() {
            if sum > max_sum {
                max_sum = sum;
                max_level = (idx + 1) as i32;
            }
        }
        
        max_level
    }

    

    pub fn level_order_rec(root: &Option<Rc<RefCell<TreeNode>>>, 
    level: usize, res: &mut Vec<i32>) {

        if let Some(node) = root {
            let node = node.borrow();

            if level >= res.len() {
                res.push(0);
            }

            res[level] += node.val;

            Self::level_order_rec(&node.left, level+1, res);
            Self::level_order_rec(&node.right, level+1, res);
        }
    }
}
```

Time: O(n)
Space: O(n)