រកផលបូកកំរិតអតិបរមានៅក្នុងមែកធាងប្រព័ន្ធគោលពីរ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
មែកធាងគោលពីរ ការស្វែងរកដំបូង ជួរ មែកធាង ការឆ្លងកាត់ដើមឈើ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ រកផលបូកកំរិតអតិបរិមាក្នុងមែកធាងគោលពីរ” ចែងថាអ្នកត្រូវបានគេអោយក មែកធាងគោលពីរ ជាមួយថ្នាំងវិជ្ជមាននិងអវិជ្ជមានរកផលបូកអតិបរមានៃកម្រិតមួយនៅក្នុងមែកធាងគោលពីរ។

ឧទាហរណ៍

បញ្ចូល
រកផលបូកកំរិតអតិបរមានៅក្នុងមែកធាងប្រព័ន្ធគោលពីរ

7

ការពន្យល់
កំរិតទីមួយ៖ ផលបូក = ៥
កំរិតទីពីរ៖ ផលបូក = (-២ + ៦) = ៤
កំរិតទីបី៖ ផលបូក = (១១ + (-៥) + ១) = ៧
កំរិតទីបួន៖ ផលបូក = (៣ + (-៣)) = ០
អតិបរមាផលបូក = ៧

ក្បួនដោះស្រាយដើម្បីរកផលបូកកំរិតអតិបរមានៅក្នុងមែកធាងប្រព័ន្ធគោលពីរ

គំនិតនេះគឺដើម្បីធ្វើត្រាប់តាមលំដាប់កម្រិតហើយសម្រាប់កម្រិតនីមួយៗគណនាផលបូកនៃថ្នាំងទាំងអស់នៃកម្រិតនោះ។ ប្រសិនបើផលបូកធំជាងផលបូកអតិបរមាធ្វើបច្ចុប្បន្នភាពផលបូកអតិបរមា។

  1. បង្កើត ជួរនិងជំរុញថ្នាំងឫសទៅជួរ។ ចាប់ផ្តើមអថេរ maxSum ជាភាពមិនពិតអវិជ្ជមាន។
  2. ខណៈពេលដែលជួរគឺមិនទទេធ្វើម្តងទៀតជំហានទី 3 និងទី 4 ។
  3. នៅពេលនេះកម្រិតមួយមានវត្តមាននៅក្នុងជួរ។ ចាប់ផ្តើមអថេរដែលមានឈ្មោះ ទំហំ ទំហំនៃជួរនិងផលបូកអថេរគឺ ០ ។
  4. ដំណើរការរង្វិលជុំពី i = 0 ទៅទំហំហើយនៅរាល់ការនិយាយឡើងវិញកើតឡើងពីធាតុមួយជួរ។ បន្ថែមតម្លៃនៃធាតុនេះទៅផលបូកអថេរនិងជំរុញកូន ៗ ដែលកើតចេញពីថ្នាំងទៅជួរ។ នៅចុងបញ្ចប់នៃរង្វិលជុំប្រសិនបើផលបូកធំជាង maxSum សូមធ្វើបច្ចុប្បន្នភាព maxSum ជាផលបូក។
  5. ត្រឡប់ maxSum ។

ការពន្យល់

ពិចារណាដើមឈើនៅក្នុងឧទាហរណ៍ខាងលើ

1 ជំហាន

បង្កើតជួរហើយរុញឫសទៅវា។ ចាប់ផ្តើមអាំងតេក្រាលអថេរអតិបរមាជាភាពមិនពិតអវិជ្ជមាន។
ជួរ = 5 និង maxSum = -infinity

2 ជំហាន

ធ្វើជំហានទី ៣ និង ៤ ម្តងទៀតខណៈពេលដែលជួរមិនទទេ។

ជំហានទី ៤ និងទី ៥

ការបែងចែក ១
ទំហំ = ១, បូក = ០
យកធាតុទាំងអស់ចេញពីជួរបន្ថែមតម្លៃនៃធាតុនីមួយៗដើម្បីបូកនិងរុញកុមារនៃធាតុទាំងអស់ទៅជួរ។
ផលបូក = ៥, ជួរ = -២ -> ៦
ធ្វើបច្ចុប្បន្នភាព maxSum ដូច្នេះ maxSum = ៥

ការបែងចែក ១
ទំហំ = ១, បូក = ០
យកធាតុទាំងអស់ចេញពីជួរបន្ថែមតម្លៃនៃធាតុនីមួយៗដើម្បីបូកនិងរុញកុមារនៃធាតុទាំងអស់ទៅជួរ។
ផលបូក = (-២ + ៦) = ៤, ជួរ = ១១ -> -៥ -> ១
ធ្វើបច្ចុប្បន្នភាព maxSum ដូច្នេះ maxSum = ៥

ការបែងចែក ១
ទំហំ = ១, បូក = ០
យកធាតុទាំងអស់ចេញពីជួរបន្ថែមតម្លៃនៃធាតុនីមួយៗដើម្បីបូកនិងរុញកុមារនៃធាតុទាំងអស់ទៅជួរ។
ផលបូក = (១១ + (-៥) + ១) = ៧, ជួរ = ៣ -> -៣
ធ្វើបច្ចុប្បន្នភាព maxSum ដូច្នេះ maxSum = ៥

ការបែងចែក ១
ទំហំ = ១, បូក = ០
យកធាតុទាំងអស់ចេញពីជួរបន្ថែមតម្លៃនៃធាតុនីមួយៗដើម្បីបូកនិងរុញកុមារនៃធាតុទាំងអស់ទៅជួរ។
បូក = (៣ + (-៣)) = ០, ជួរ = គ្មាន
ធ្វើបច្ចុប្បន្នភាព maxSum ដូច្នេះ maxSum = ៥

នៅពេលជួរក្លាយជាទទេដូច្នេះយើងឈប់ហើយផលបូកនៃកម្រិតគឺ ៧ ។

លេខកូដ

កូដចាវ៉ាដើម្បីរកផលបូកកំរិតអតិបរមានៅក្នុងមែកធាងប្រព័ន្ធគោលពីរ

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), ដោយសារតែយើងបានប្រើជួរដើម្បីរក្សាទុកធាតុនៃកម្រិតនីមួយៗ។ ភាពស្មុគស្មាញនៃអវកាសក៏ជាលីនេអ៊ែរផងដែរ។