Рубрики

Найти максимальную сумму уровня в бинарном дереве

Учитывая, что двоичное дерево имеет положительные и отрицательные узлы, задача состоит в том, чтобы найти в нем максимальный уровень суммы.

Примеры:

Input :               4
                    /   \
                   2    -5
                  / \    /\
                -1   3 -2  6
Output: 6
Explanation :
Sum of all nodes of 0'th level is 4
Sum of all nodes of 1'th level is -3
Sum of all nodes of 0'th level is 6
Hence maximum sum is 6

Input :          1
               /   \
             2      3
           /  \      \
          4    5      8
                    /   \
                   6     7  
Output :  17

Эта проблема является вариацией проблемы максимальной ширины . Идея состоит в том, чтобы сделать обход уровня дерева. При выполнении обхода обрабатывайте узлы разного уровня отдельно. Для каждого обрабатываемого уровня вычисляют сумму узлов на уровне и отслеживают максимальную сумму.

// Программа C ++ на основе очереди, чтобы найти максимальную сумму
// уровня в двоичном дереве
#include<bits/stdc++.h>

using namespace std ;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct Node

{

    int data ;

    struct Node * left, * right ;

};

  
// Функция для поиска максимальной суммы уровня в дереве
// используя обход уровня

int maxLevelSum(struct Node * root)

{

    // Базовый вариант

    if (root == NULL)

        return 0;

  

    // Инициализировать результат

    int result = root->data;

  

    // Делаем ли вы прохождение ордера, отслеживая число

    // узлов на каждом уровне.

    queue<Node*> q;

    q.push(root);

    while (!q.empty())

    {

        // Получить размер очереди при порядке уровней

        // обход одного уровня

        int count = q.size() ;

  

        // Итерация для всех узлов в очереди в настоящее время

        int sum = 0;

        while (count--)

        {

            // Выводим узел из очереди

            Node *temp = q.front();

            q.pop();

  

            // Добавить значение этого узла к текущей сумме.

            sum = sum + temp->data;

  

            // ставим в очередь левых и правых потомков

            // удаленный узел

            if (temp->left != NULL)

                q.push(temp->left);

            if (temp->right != NULL)

                q.push(temp->right);

        }

  

        // Обновляем максимальное количество узлов

        result = max(sum, result);

    }

  

    return result;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct Node * newNode(int data)

{

    struct Node * node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return (node);

}

  

int main()

{

    struct Node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(3);

    root->left->left  = newNode(4);

    root->left->right = newNode(5);

    root->right->right = newNode(8);

    root->right->right->left  = newNode(6);

    root->right->right->right  = newNode(7);

  

    / * Построенное двоичное дерево это:

                 1

               / /

             2 3

           ///

          4 5 8

                    / /

                   6 7 * /

    cout << "Maximum level sum is "

         << maxLevelSum(root) << endl;

    return 0;

}

Выход :

Maximum level sum is 17

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти максимальную сумму уровня в бинарном дереве

0.00 (0%) 0 votes