1161.最大层内元素和

链接：1161.最大层内元素和
难度：Medium
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

题解 1 - rust

• 编辑时间：2022-08-01
• 执行用时：24ms
• 内存消耗：3.2MB
• 编程语言：rust
• 解法介绍：层序遍历。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        use std::collections::VecDeque;
        let root = root.unwrap();
        let mut q: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
        q.push_back(root.clone());
        let (mut max_level, mut max_sum, mut cur, mut size, mut level) =
            (1, root.borrow().val, 0, 1, 1);
        while let Some(node) = q.pop_front() {
            if node.as_ref().borrow().left.is_some() {
                cur += node.as_ref().borrow().left.as_ref().unwrap().borrow().val;
                q.push_back(node.as_ref().borrow().left.as_ref().unwrap().clone());
            }
            if node.as_ref().borrow().right.is_some() {
                cur += node.as_ref().borrow().right.as_ref().unwrap().borrow().val;
                q.push_back(node.as_ref().borrow().right.as_ref().unwrap().clone());
            }
            size -= 1;
            if size == 0 {
                size = q.len();
                level += 1;
                if size > 0 && cur > max_sum {
                    max_sum = cur;
                    max_level = level;
                }
                cur = 0;
            }
        }
        max_level
    }
}

题解 2 - cpp

• 编辑时间：2022-08-01
• 执行用时：156ms
• 内存消耗：104.7MB
• 编程语言：cpp
• 解法介绍：层序遍历。

class Solution {
   public:
    int maxLevelSum(TreeNode *root) {
        queue<TreeNode *> q;
        q.push(root);
        int max_level = 1, max_sum = root->val, cur = 0, size = 1, level = 1;
        while (q.size()) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left) {
                cur += node->left->val;
                q.push(node->left);
            }
            if (node->right) {
                cur += node->right->val;
                q.push(node->right);
            }
            if (--size == 0) {
                size = q.size();
                level++;
                if (size > 0 && cur > max_sum) {
                    max_sum = cur;
                    max_level = level;
                }
                cur = 0;
            }
        }
        return max_level;
    }
};