1161. Maximum Level Sum of a Binary Tree

LeetCode medium оригинал: C# #csharp #graph #leetcode #medium #queue #tree #two-pointers

LeetCode Static

Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.

Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.

Пример:

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.

C# решение

сопоставлено/оригинал

public class Solution {
    public int MaxLevelSum(TreeNode root) {
        int maxSum = int.MinValue;
        int ans = 0, level = 0;
        Queue<TreeNode> q = new Queue<TreeNode>();
        
        q.Enqueue(root);
        
        while (q.Count > 0) {
            level++;
            int sumAtCurrentLevel = 0;
            for (int sz = q.Count; sz > 0; --sz) {
                TreeNode node = q.Dequeue();
                sumAtCurrentLevel += node.val;
                if (node.left != null) {
                    q.Enqueue(node.left);
                }
                if (node.right != null) {
                    q.Enqueue(node.right);
                }
            }
            
            if (maxSum < sumAtCurrentLevel) {
                maxSum = sumAtCurrentLevel;
                ans = level;
            }
        }
        
        return ans;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxLevelSum(TreeNode root) {
        int maxSum = int.MinValue;
        int ans = 0, level = 0;
        queue<TreeNode> q = new queue<TreeNode>();
        
        q.Enqueue(root);
        
        while (q.size() > 0) {
            level++;
            int sumAtCurrentLevel = 0;
            for (int sz = q.size(); sz > 0; --sz) {
                TreeNode node = q.Dequeue();
                sumAtCurrentLevel += node.val;
                if (node.left != null) {
                    q.Enqueue(node.left);
                }
                if (node.right != null) {
                    q.Enqueue(node.right);
                }
            }
            
            if (maxSum < sumAtCurrentLevel) {
                maxSum = sumAtCurrentLevel;
                ans = level;
            }
        }
        
        return ans;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MaxLevelSum(TreeNode root) {
        int maxSum = int.MinValue;
        int ans = 0, level = 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        
        q.Enqueue(root);
        
        while (q.size() > 0) {
            level++;
            int sumAtCurrentLevel = 0;
            for (int sz = q.size(); sz > 0; --sz) {
                TreeNode node = q.poll();
                sumAtCurrentLevel += node.val;
                if (node.left != null) {
                    q.Enqueue(node.left);
                }
                if (node.right != null) {
                    q.Enqueue(node.right);
                }
            }
            
            if (maxSum < sumAtCurrentLevel) {
                maxSum = sumAtCurrentLevel;
                ans = level;
            }
        }
        
        return ans;
    }
}

JavaScript решение

сопоставлено/оригинал

var maxLevelSum = function(root) {
    let maxSum = -Infinity;
    let ans = 0, level = 0;
    let q = [root];
    
    while (q.length > 0) {
        level++;
        let sumAtCurrentLevel = 0;
        for (let sz = q.length; sz > 0; --sz) {
            let node = q.shift();
            sumAtCurrentLevel += node.val;
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        
        if (maxSum < sumAtCurrentLevel) {
            maxSum = sumAtCurrentLevel;
            ans = level;
        }
    }
    
    return ans;
};

Python решение

сопоставлено/оригинал

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        maxSum = float('-inf')
        ans = 0
        level = 0
        q = deque([root])
        
        while q:
            level += 1
            sumAtCurrentLevel = 0
            for _ in range(len(q)):
                node = q.popleft()
                sumAtCurrentLevel += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            if maxSum < sumAtCurrentLevel:
                maxSum = sumAtCurrentLevel
                ans = level
        
        return ans

Go решение

сопоставлено/оригинал

func maxLevelSum(root *TreeNode) int {
    maxSum := math.MinInt32
    ans := 0
    level := 0
    q := []*TreeNode{root}
    
    for len(q) > 0 {
        level++
        sumAtCurrentLevel := 0
        nextQ := []*TreeNode{}
        for _, node := range q {
            sumAtCurrentLevel += node.Val
            if node.Left != nil {
                nextQ = append(nextQ, node.Left)
            }
            if node.Right != nil {
                nextQ = append(nextQ, node.Right)
            }
        }
        q = nextQ
        
        if maxSum < sumAtCurrentLevel {
            maxSum = sumAtCurrentLevel
            ans = level
        }
    }
    
    return ans
}

Algorithm

Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.

Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.

После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.