იპოვნეთ მაქსიმალური დონის ჯამი Binary Tree- ში


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon
ორობითი ხე სიგანე პირველი ძებნა Queue ხე ხის გადაკვეთა

პრობლემის განცხადება

პრობლემა "იპოვნეთ მაქსიმალური დონის ჯამი ორობით ხეში" აღნიშნავს, რომ თქვენ გეძლევათ ა ორობითი ხე დადებითი და უარყოფითი კვანძებით, იპოვნეთ დონის მაქსიმალური ჯამი ორობით ხეში.

მაგალითი

შეყვანის
იპოვნეთ მაქსიმალური დონის ჯამი Binary Tree- ში

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 =-უსასრულო

ნაბიჯი 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.

კოდი

ჯავის კოდი ორობითი ხის მაქსიმალური დონის ჯამის მოსაძიებლად

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), რადგან თითოეული დონის ელემენტების შესანახად გამოვიყენეთ რიგი. სივრცის სირთულე ასევე ხაზოვანია.