1161. Maximum Level Sum of a Binary Tree
題目：
求一棵樹擁有最大和的層
思路：
BFS 進階題
基本上還是跑 BFS
但要記錄最大和並每層更新
如果比較大就更新最大層數
層數也要每輪加一
就是個稍微多一些東西要處理的 BFS
Code:
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut max_level_sum = i32::MIN;
let mut curr_level = 1;
let mut max_level = 1;
let mut queue = VecDeque::new();
if let Some(node) = root {
queue.push_back(node);
}
while !queue.is_empty() {
let level_len = queue.len();
let mut local_level_sum = 0;
for _ in 0..level_len {
if let Some(node) = queue.pop_front() {
let mut n_borrow = node.borrow_mut();
local_level_sum += n_borrow.val;
if let Some(left) = n_borrow.left.take() {
queue.push_back(left);
}
if let Some(right) = n_borrow.right.take() {
queue.push_back(right);
}
}
}
if local_level_sum > max_level_sum {
max_level_sum = local_level_sum;
max_level = curr_level;
}
curr_level += 1;
}
max_level
}
}