Пронајдете збир на максимално ниво во Бинарно дрво


Ниво на тешкотија Медиум
Често прашувано во Амазон
Бинарно дрво Прво пребарување на ширина редот Дрво Преминување на дрвото

Изјава за проблем

Проблемот „Пронајди ја збирот на максималното ниво во бинарното дрво“ наведува дека ти е дадена 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 и максимум = = бесконечност

Чекор 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

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

Временска комплексност

НА), затоа што едноставно ги прегазивме сите елементи на дрвото и ги турнавме двапати во редот. Значи, временската сложеност е линеарна.

Комплексноста на просторот

НА), затоа што користевме редица за складирање на елементите на секое ниво. Комплексноста на просторот е исто така линеарна.