Знайдзіце максімальную суму ўзроўню ў двайковым дрэве


Узровень складанасці серада
Часта пытаюцца ў амазонка
Двайковае дрэва Шырыня Першы пошук чаргу дрэва Абход дрэва

Пастаноўка праблемы

Праблема «Знайсці максімальную суму ўзроўню ў двайковым дрэве» абвяшчае, што вам дадзена бінарнае дрэва з станоўчымі і адмоўнымі вузламі знайдзіце максімальную суму ўзроўню ў двайковым дрэве.

Прыклад

уваход
Знайдзіце максімальную суму ўзроўню ў двайковым дрэве

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

Аналіз складанасці

Складанасць часу

O (N), таму што мы проста прайшлі па ўсіх элементах дрэва і двойчы прасунулі іх у чаргу. Такім чынам, складанасць часу лінейная.

Касмічная складанасць

O (N), таму што мы выкарыстоўвалі чаргу для захоўвання элементаў кожнага ўзроўню. Складанасць касмічнай прасторы таксама лінейная.