Намерете максимална сума на ниво в двоично дърво


Ниво на трудност M
Често задавани в Амазонка
Двоично дърво Широчина Първо търсене Опашка Дърво Обръщане на дърво

Декларация за проблема

Проблемът „Намиране на максимално ниво на сумата в двоично дърво“ гласи, че сте получили 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

Създайте опашка и натиснете корен към нея. Инициализирайте променлива 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

C ++ код за намиране на максимално ниво на сумата в двоично дърво

#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

Анализ на сложността

Сложност във времето

НА), защото просто прекосихме всички елементи на дървото и ги натиснахме два пъти в опашката. Така че сложността на времето е линейна.

Сложност на пространството

НА), защото използвахме опашка за съхраняване на елементите на всяко ниво. Сложността на пространството също е линейна.