Знайдіть максимальну суму рівня в двійковому дереві


Рівень складності Medium
Часто запитують у Амазонка
Бінарне дерево Ширина - перший пошук Чергу Дерево Обхід дерева

Постановка проблеми

У задачі “Знайти максимальну суму рівня в двійковому дереві” зазначено, що вам дано a двійкове дерево з позитивними та негативними вузлами знайдіть максимальну суму рівня в двійковому дереві.

Приклад

вхід
Знайдіть максимальну суму рівня в двійковому дереві

7

Пояснення
Перший рівень: Сума = 5
Другий рівень: Сума = (-2 + 6) = 4
Третій рівень: Сума = (11 + (-5) + 1) = 7
Четвертий рівень: Сума = (3 + (-3)) = 0
Максимальна сума = 7

Алгоритм пошуку суми максимального рівня в двійковому дереві

Ідея полягає в тому, щоб зробити обхід порядку порядку і для кожного рівня обчислити суму всіх вузлів цього рівня. Якщо сума перевищує максимальну суму, оновіть максимальну суму.

  1. Створити чергу, і відсуньте кореневий вузол до черги. Ініціалізуйте змінну maxSum як негативна нескінченність.
  2. Поки черга не порожня, повторіть кроки 3 та 4.
  3. На даний момент в черзі присутній один рівень. Ініціалізуйте змінну з іменем розмір як розмір черги та змінна сума як 0.
  4. Запустіть цикл від i = 0 до розміру, і на кожній ітерації вискакуйте елемент із черги. Додайте значення цього елемента до змінної суми і витягніть дочерній елемент вискакувального вузла в чергу. В кінці циклу, якщо сума перевищує maxSum, оновіть maxSum як суму.
  5. Повернення maxSum.

Пояснення

Розглянемо дерево у прикладі вище

крок 1

Створіть чергу та натисніть на неї root. Ініціалізуйте змінну maxSum як негативну нескінченність.
черга = 5 і maxSum = -нескінченність

крок 2

Повторіть кроки 3 і 4, поки черга не порожня.

Крок 3 і 4

ітерація 1
розмір = 1, сума = 0
Видаліть усі елементи з черги, додайте значення кожного елемента для підсумовування та висуньте дочірні елементи кожного елемента в чергу.
сума = 5, черга = -2 -> 6
Оновіть maxSum, отже, maxSum = 5

ітерація 2
розмір = 2, сума = 0
Видаліть усі елементи з черги, додайте значення кожного елемента для підсумовування та висуньте дочірні елементи кожного елемента в чергу.
сума = (-2 + 6) = 4, черга = 11 -> -5 -> 1
Оновіть maxSum, отже, maxSum = 5

ітерація 3
розмір = 3, сума = 0
Видаліть усі елементи з черги, додайте значення кожного елемента для підсумовування та висуньте дочірні елементи кожного елемента в чергу.
сума = (11 + (-5) + 1) = 7, черга = 3 -> -3
Оновіть maxSum, отже, maxSum = 7

ітерація 4
розмір = 2, сума = 0
Видаліть усі елементи з черги, додайте значення кожного елемента для підсумовування та висуньте дочірні елементи кожного елемента в чергу.
сума = (3 + (-3)) = 0, черга = нуль
Оновіть maxSum, отже, maxSum = 7

Коли черга стає порожньою, ми зупиняємось, і максимальна сума рівня дорівнює 7.

код

Код Java для пошуку суми максимального рівня в двійковому дереві

import java.util.LinkedList;
import java.util.Queue;

class FindMaximumLevelSumInBinaryTree {
    // class representing node of binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int maxLevelSum(Node root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }       
        // create a queue and push root to it
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        // initialize maxSum as negative infinity 
        int maxSum = Integer.MIN_VALUE;
        
        // while queue is not empty
        while (!queue.isEmpty()) {
            // At this moment the queue contains one level in it
            // initialize size as size of queue
            int size = queue.size();
            // initialize sum as 0, this represents the sum of a level
            int sum = 0;
            // run a loop from 0 to size
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = queue.poll();
                // add the value of current element to sum
                sum += curr.data;
                
                // push the children of current element to queue
                if (curr.left != null)
                    queue.add(curr.left);
                
                if (curr.right != null)
                    queue.add(curr.right);
            }

            // update max sum
            maxSum = Math.max(maxSum, sum);
        }
        
        // return max sum
        return maxSum;
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(5);
        root.left = new Node(-2);
        root.right = new Node(6);
        root.left.left = new Node(11);
        root.right.left = new Node(-5);
        root.right.right = new Node(1);
        root.right.right.left = new Node(3);
        root.right.right.right = new Node(-3);

        System.out.println(maxLevelSum(root));
    }
}
7

Код С ++ для пошуку суми максимального рівня в двійковому дереві

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

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int maxLevelSum(Node *root) {
    if (root == NULL) {
        return INT_MIN;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialize maxSum as negative infinity
    int maxSum = INT_MIN;
    
    // while queue is not empty
    while (!q.empty()) {
        // At this moment the queue contains one level in it
        // initialize size as size of queue
        int size = q.size();
        // initialize sum as 0, this represents the sum of a level
        int sum = 0;
        
        // run a loop from 0 to size
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            q.pop();
            // add the value of current element to sum
            sum += curr->data;
            
            // push the children of current element to queue
            if (curr->left != NULL)
                q.push(curr->left);
                
            if (curr->right != NULL)
                q.push(curr->right);
        }
        
        // update max sum
        maxSum = std::max(maxSum, sum);
    }
    
    // return max sum
    return maxSum;
}

int main() {
    // Example tree
    Node *root = newNode(5);
    root->left = newNode(-2);
    root->right = newNode(6);
    root->left->left = newNode(11);
    root->right->left = newNode(-5);
    root->right->right = newNode(1);
    root->right->right->left = newNode(3);
    root->right->right->right = newNode(-3);
    
    cout<<maxLevelSum(root)<<endl;
    
    return 0;
}
7

Аналіз складності

Складність часу

O (N), тому що ми просто обходили всі елементи дерева і двічі штовхали їх у чергу. Тож часова складність є лінійною.

Складність простору

O (N), тому що ми використовували чергу для зберігання елементів кожного рівня. Складність простору також лінійна.