Рубрики

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

Для заданного двоичного дерева найдите максимальную сумму вертикального уровня в двоичном дереве.

Примеры:

Input : 
                3
              /  \
             4    6
           /  \  /  \
         -1   -2 5   10
                  \
                   8  

Output : 14
Vertical level having nodes 6 and 8 has maximum
vertical sum 14. 

Input :
                1
              /  \
             5    8
           /  \    \
          2   -6    3
           \       /
           -1     -4
             \
              9

Output : 4

Рекомендуется: пожалуйста, попробуйте сначала свой подход к IDE, а затем посмотрите на решение.

Простое решение — сначала найти сумму вертикального уровня каждого уровня, начиная с минимального вертикального уровня до максимального вертикального уровня. Нахождение суммы одного вертикального уровня занимает O (n) времени. В худшем случае временная сложность этого решения составляет O (n ^ 2).

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

Ниже приведена реализация вышеуказанного подхода:

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

using namespace std;

  
// Узел двоичного дерева

struct Node {

    int data;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового
// Узел двоичного дерева

struct Node* newNode(int item)

{

    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

    temp->data = item;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Функция для поиска максимальной вертикальной суммы
// в двоичном дереве.

int maxVerticalSum(Node* root)

{

    if (root == NULL) {

        return 0;

    }

  

    // Для хранения суммы каждого вертикального уровня.

    unordered_map<int, int> verSum;

  

    // Для хранения максимальной суммы вертикального уровня.

    int maxSum = INT_MIN;

  

    // Для сохранения вертикального уровня текущего узла.

    int currLev;

  

    // Очередь на выполнение обхода уровня.

    // Каждый элемент очереди представляет собой пару узлов

    // и его вертикальный уровень.

    queue<pair<Node*, int> > q;

    q.push({ root, 0 });

  

    while (!q.empty()) {

  

        // Извлечение узла в начале очереди

        // и его вертикальный уровень.

        root = q.front().first;

        currLev = q.front().second;

        q.pop();

  

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

        // вертикальный уровень до которого

        // текущий узел принадлежит.

        verSum[currLev] += root->data;

  

        if (root->left)

            q.push({ root->left, currLev - 1 });

  

        if (root->right)

            q.push({ root->right, currLev + 1 });

    }

  

    // Найти максимальную сумму вертикального уровня.

    for (auto it : verSum) 

        maxSum = max(maxSum, it.second);

     

    return maxSum;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / *

                3

              / /

             4 6

           / / / /

         -1 -2 5 10

                  /

                   8

    * /

  

    struct Node* root = newNode(3);

    root->left = newNode(4);

    root->right = newNode(6);

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

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

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

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

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

  

    cout << maxVerticalSum(root);

    return 0;

}

Выход:

14

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

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

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

0.00 (0%) 0 votes