مجموع حداکثر سطح را در Binary Tree پیدا کنید  


سطح دشواری متوسط
اغلب در آمازون
درخت باینری عرض اول جستجو صف درخت عبور از درخت

بیان مسأله  

مسئله "پیدا کردن مقدار حداکثر سطح در درخت باینری" بیان می کند که به شما داده می شود درخت دودویی با گره های مثبت و منفی ، حداکثر حاصل از یک سطح را در درخت باینری پیدا کنید.

مثال  

ورودی
مجموع حداکثر سطح را در Binary Tree پیدا کنیدسنجاق

7

توضیح
سطح اول: جمع = 5
سطح دوم: جمع = (-2 + 6) = 4
سطح سوم: جمع = (11 + (-5) + 1) = 7
سطح چهارم: جمع = (3 + (-3)) = 0
حداکثر مجموع = 7

الگوریتم یافتن مقدار حداکثر سطح در درخت باینری  

ایده این است که یک پیمایش مرتب سازی سطح انجام دهید و برای هر سطح جمع کل گره های آن سطح را محاسبه کنید. اگر مجموع بیشتر از حداکثر جمع است ، حداکثر مجموع را به روز کنید.

  1. ایجاد یک صف، و گره ریشه را به صف فشار دهید. شروع یک متغیر حداکثر جمع به عنوان بی نهایت منفی
  2. در حالی که صف خالی نیست مرحله 3 و 4 را تکرار کنید.
  3. در این لحظه یک سطح در صف وجود دارد. یک متغیر با نام اولیه را شروع کنید اندازه به عنوان اندازه صف و یک مقدار متغیر به عنوان 0.
  4. یک حلقه از i = 0 به اندازه اجرا کنید و در هر تکرار یک عنصر از صف بیرون بیاورید. مقدار این عنصر را به مقدار متغیر اضافه کنید و کودکان گره بیرون آمده را به صف فشار دهید. در پایان حلقه اگر مقدار از maxSum بیشتر باشد ، maxSum را به صورت sum به روز کنید.
  5. maxSum را برگردانید.
همچنین مشاهده کنید
جمع ترکیبی

توضیح

درخت را در مثال بالا در نظر بگیرید

1 گام

یک صف ایجاد کنید و به آن ریشه بزنید. مقدار maxSum متغیر را به عنوان بی نهایت منفی آغاز کنید.
صف = 5 و maxSum =-بی نهایت

2 گام

مرحله 3 و 4 را تکرار کنید ، در حالی که صف خالی نیست.

مرحله 3 و 4

تکرار 1
اندازه = 1 ، جمع = 0
همه عناصر را از صف خارج کنید ، مقدار هر عنصر را به جمع اضافه کنید و کودکان هر عنصر را به صف فشار دهید.
جمع = 5 ، صف = -2 -> 6
maxSum را به روز کنید ، بنابراین ، maxSum = 5

تکرار 2
اندازه = 2 ، جمع = 0
همه عناصر را از صف خارج کنید ، مقدار هر عنصر را به جمع اضافه کنید و کودکان هر عنصر را به صف فشار دهید.
sum = (-2 + 6) = 4 ، صف = 11 -> -5 -> 1
maxSum را به روز کنید ، بنابراین ، maxSum = 5

تکرار 3
اندازه = 3 ، جمع = 0
همه عناصر را از صف خارج کنید ، مقدار هر عنصر را به جمع اضافه کنید و کودکان هر عنصر را به صف فشار دهید.
جمع = (11 + (-5) + 1) = 7 ، صف = 3 -> -3
maxSum را به روز کنید ، بنابراین ، maxSum = 7

تکرار 4
اندازه = 2 ، جمع = 0
همه عناصر را از صف خارج کنید ، مقدار هر عنصر را به جمع اضافه کنید و کودکان هر عنصر را به صف فشار دهید.
sum = (3 + (-3)) = 0 ، صف = null
maxSum را به روز کنید ، بنابراین ، maxSum = 7

با خالی شدن صف ، ما متوقف می شویم و حداکثر یک سطح 7 است.

رمز  

جاوا کد برای یافتن مقدار حداکثر سطح در Binary Tree

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 ++ برای یافتن مقدار حداکثر سطح در Binary Tree

#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

تحلیل پیچیدگی  

پیچیدگی زمان

بر)، زیرا ما به راحتی تمام عناصر درخت را رد کردیم و آنها را دو بار در صف هل دادیم. بنابراین پیچیدگی زمان خطی است.

همچنین مشاهده کنید
واژگان فردی را معکوس کنید

پیچیدگی فضا

بر)، زیرا ما از صف برای ذخیره عناصر هر سطح استفاده کردیم. پیچیدگی فضا نیز خطی است.