Эки дарактын максималдуу деңгээлинин суммасын табыңыз


Кыйынчылык деңгээли орто
Көп суралган Amazon
Binary Tree Биринчи издөө кезек дарак Tree Traversal

Маселени билдирүү

"Эки дарактын максималдуу деңгээлинин суммасын табуу" көйгөйүндө сизге а берилген экилик дарак оң жана терс түйүндөр менен, экилик дарактын деңгээлинин максималдуу суммасын табыңыз.

мисал

кирүү
Эки дарактын максималдуу деңгээлинин суммасын табыңыз

7

түшүндүрүү
Биринчи деңгээл: сумма = 5
Экинчи деңгээл: Сум = (-2 + 6) = 4
Үчүнчү деңгээл: Сум = (11 + (-5) + 1) = 7
Төртүнчү деңгээл: Сум = (3 + (-3)) = 0
Max Sum = 7

Эки дарактын максималдуу деңгээлинин суммасын табуу алгоритми

Идея денгээлдин буйругун өтүү жана ар бир деңгээл үчүн ошол деңгээлдеги бардык түйүндөрдүн суммасын эсептөө. Эгерде сумма максималдуу суммадан чоң болсо, анда эң чоң сумманы жаңыртыңыз.

  1. түзүү кезек, жана тамыр түйүнүн кезекке түрт. Өзгөрүлмө инициализациялоо maxSum терс чексиздик катары.
  2. Кезек бош эмес болсо дагы, 3 жана 4-кадамдарды кайталаңыз.
  3. Учурда бир деңгээл кезекте турат. Аттуу өзгөрмө инициализациялоо көлөм кезектин өлчөмү жана 0 өзгөрмө суммасы.
  4. I = 0 ден чоңдукка чейин циклди иштетип, ар бир кайталанганда кезектеги элементтерди чыгарыңыз. Бул элементтин маанисин өзгөрүлмө суммага кошуп, чыккан түйүндүн балдарын кезекке тургузуңуз. Циклдин аягында сумма maxSum дан чоң болсо, maxSum сумманы жаңыртыңыз.
  5. MaxSum кайтаруу.

түшүндүрүү

Жогорудагы мисалдагы бакты карап көрөлү

Step 1

Кезек түзүп, ага тамыр салыңыз. MaxSum өзгөрмөсүн терс чексиздик катары баштаңыз.
кезек = 5 жана maxSum = -чексиздик

Step 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), анткени биз ар бир деңгээлдеги элементтерди сактоо үчүн кезек колдонгонбуз. Космостун татаалдыгы дагы сызыктуу.