Βρείτε το άθροισμα μέγιστου επιπέδου στο δυαδικό δέντρο


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα
Δυαδικό δέντρο Πρώτη αναζήτηση Ουρά Δέντρο Διασχίζοντας το δέντρο

Δήλωση προβλήματος

Το πρόβλημα "Εύρεση μέγιστου επιπέδου στο δυαδικό δέντρο" δηλώνει ότι σας δίνεται ένα δυαδικό δέντρο με θετικούς και αρνητικούς κόμβους, βρείτε το μέγιστο άθροισμα ενός επιπέδου στο δυαδικό δέντρο.

Παράδειγμα

Εισαγωγή
Βρείτε το άθροισμα μέγιστου επιπέδου στο δυαδικό δέντρο

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 βήμα

Δημιουργήστε μια ουρά και σπρώξτε το root. Αρχικοποιήστε μια μεταβλητή maxSum ως αρνητικό άπειρο.
ουρά = 5 και maxSum = -infinity

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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί απλά διασχίσαμε όλα τα στοιχεία του δέντρου και τα σπρώξαμε δύο φορές στην ουρά. Έτσι η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

ΕΠΙ), γιατί χρησιμοποιήσαμε την ουρά για να αποθηκεύσουμε τα στοιχεία κάθε επιπέδου. Η πολυπλοκότητα του διαστήματος είναι επίσης γραμμική.