1161. Maximum Level Sum of a Binary Tree

Description of Problem

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Example 1:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 104].
-10^5 <= Node.val <= 10^5

Solution

Tags: Breadth First Search

Explanation

Use the same manner in 199. Binary Tree Right Side View.

Code

// 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;
use std::collections::VecDeque;
impl Solution {
    pub fn level_with_max_sum_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut queue1 = VecDeque::new();
        let mut queue2 = VecDeque::new();
        let mut max_sum = i32::MIN;
        let (mut level, mut level_with_max_sum) = (0,0);

        if let Some(node) = root{
            queue1.push_back(Some(node));
        }   
        
        while !queue1.is_empty(){
            level+=1;
            let mut sum = 0;
            while let Some(Some(node)) = queue1.pop_front(){
                let node = node.borrow();
                sum += node.val;
                let left = node.left.clone();
                let right = node.right.clone();
                if left.is_some(){
                    queue2.push_back(left);
                }
                if right.is_some(){
                    queue2.push_back(right);
                }
            }
            if sum > max_sum {
                max_sum = sum;
                level_with_max_sum = level
            }

            let temp = queue1;
            queue1 = queue2;
            queue2 = temp;
        }

        return level_with_max_sum;
    }
}

Complexity

n is the number of nodes in tree
h is the height of tree

Time Complexity

\( T(n) = \Theta(n) \)

Auxiliary Space

\( S(h) = O(2^h) \)

Leetbook