Ҷамъи максималии сатҳи дарахти дутарафаро ёбед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon
Дарахти дуӣ Ҷустуҷӯи аввалини васеъ навбат Дарахт Траверсал дарахт

Изҳороти мушкилот

Масъалаи "Ҷамъоварии максималии сатҳи дарахти дуӣ" нишон медиҳад, ки ба шумо 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 ва 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), зеро мо барои нигоҳ доштани унсурҳои ҳар як сатҳ навбат истифода кардем. Мураккабии фазо низ хаттӣ аст.