Нађите максимум нивоа у Бинарном стаблу  


Ниво тешкоће Средњи
Често питани у амазонка
Бинарно дрво Претрага у ширину Ред Дрво Прелазак дрвета

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

Проблем „Пронађи збир максималног нивоа у бинарном стаблу“ наводи да сте добили а бинарно стабло са позитивним и негативним чворовима, пронађите максимални збир нивоа у бинарном стаблу.

Пример  

Улазни
Нађите максимум нивоа у Бинарном стаблуПин

7

Објашњење
Први ниво: Збир = 5
Други ниво: Збир = (-2 + 6) = 4
Трећи ниво: Збир = (11 + (-5) + 1) = 7
Четврти ниво: Збир = (3 + (-3)) = 0
Максимална сума = 7

Алгоритам за проналажење суме максималног нивоа у бинарном стаблу  

Идеја је да се изврши прелазак редоследа нивоа и за сваки ниво се израчуна зброј свих чворова тог нивоа. Ако је збир већи од максималног збира, ажурирајте максимални збир.

  1. Креирање ред, и гурните коријенски чвор у ред. Иницијализујте променљиву макСум као негативна бесконачност.
  2. Иако ред није празан, поновите кораке 3 и 4.
  3. Тренутно је један ниво присутан у реду. Иницијализујте променљиву са именом величина као величина реда и променљива сума као 0.
  4. Покрените петљу од и = 0 до величине и на свакој итерацији искочите елемент из реда. Додајте вредност овог елемента променљивој суми и потисните потомке искоченог чвора у ред. На крају петље ако је збир већи од макСум, ажурирајте макСум као збир.
  5. Врати макСум.
Види такође
Комбинација Збир

Објашњење

Размотрите стабло у горњем примеру

Корак КСНУМКС

Направите ред и гурните роот до њега. Иницијализујте променљиву макСум као негативну бесконачност.
ред = 5 и макСум =-бесконачност

Корак КСНУМКС

Поновите 3. и 4. корак, док ред није празан.

Корак 3 и 4

понављање КСНУМКС
величина = 1, сума = 0
Уклоните све елементе из реда, додајте вредност сваког елемента у зброј и потисните подређене елементе у ред.
сума = 5, ред = -2 -> 6
Ажурирајте макСум, дакле, макСум = 5

понављање КСНУМКС
величина = 2, сума = 0
Уклоните све елементе из реда, додајте вредност сваког елемента у зброј и потисните подређене елементе у ред.
збир = (-2 + 6) = 4, ред = 11 -> -5 -> 1
Ажурирајте макСум, дакле, макСум = 5

понављање КСНУМКС
величина = 3, сума = 0
Уклоните све елементе из реда, додајте вредност сваког елемента у зброј и потисните подређене елементе у ред.
збир = (11 + (-5) + 1) = 7, ред = 3 -> -3
Ажурирајте макСум, дакле, макСум = 7

понављање КСНУМКС
величина = 2, сума = 0
Уклоните све елементе из реда, додајте вредност сваког елемента у зброј и потисните подређене елементе у ред.
сума = (3 + (-3)) = 0, ред = нулл
Ажурирајте макСум, дакле, макСум = 7

Како ред постаје празан, тако се заустављамо и максимални збир нивоа је 7.

код  

Јава код за проналажење суме максималног нивоа у бинарном стаблу

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

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

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

НА), јер смо једноставно прешли преко свих елемената стабла и два пута их гурнули у ред. Дакле, временска сложеност је линеарна.

Види такође
Обратите поједине речи

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

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