វិធីសាស្រ្តស្មុគស្មាញក្នុងការរកកំពស់ដើមឈើគោលពីរ  


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ គួរឱ្យគោរព កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon និយមជ្រុល Fourkites ការដំឡើង Snapdeal Yatra
មែកធាងគោលពីរ ជួរ មែកធាង

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

បញ្ហា“ វិធីសាស្រ្តចំឡែកក្នុងការស្វែងរកកំពស់ដើមឈើគោល” បញ្ជាក់ថាអ្នកត្រូវបានគេអោយ មែកធាងគោលពីរ, រកឃើញកំពស់ដើមឈើដោយប្រើវិធីសាស្ត្រដដែលៗ។

ឧទាហរណ៍  

បញ្ចូល
វិធីសាស្រ្តស្មុគស្មាញក្នុងការរកកំពស់ដើមឈើគោលពីរពិន

3

បញ្ចូល
វិធីសាស្រ្តស្មុគស្មាញក្នុងការរកកំពស់ដើមឈើគោលពីរពិន

4

ក្បួនដោះស្រាយសម្រាប់វិធីសាស្ត្រត្រិះរិះដើម្បីរកកំពស់ដើមឈើគោលពីរ  

កម្ពស់ដើមឈើមួយក៏ស្មើនឹងកំពស់ដែរ ចំនួនកម្រិត នៅក្នុងដើមឈើ។ ដូច្នេះដើម្បីរកកម្ពស់ដោយប្រើ iteration ធ្វើ a កម្រិតលំដាប់ឆ្លងកាត់ នៃមែកធាងនិងរាប់ចំនួនកម្រិតនៅក្នុងវា។

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

ការពន្យល់

ពិចារណាដើមឈើដែលបង្ហាញក្នុងឧទាហរណ៍ដំបូង

ជំហាន 1:

រុញឫសទៅជួរហើយចាប់ផ្តើមកំពស់ជា ០ នោះគឺ
ជួរ = 2, កម្ពស់ = 0

ជំហាន 2:

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

សូម​មើល​ផង​ដែរ
លំដាប់នៃប្រវែងដែលបានផ្តល់ឱ្យដែលរាល់ធាតុគឺច្រើនជាងឬស្មើពីរដងនៃធាតុមុន

ជំហានទី ៦ និង ៧៖

ផ្នែកទី ១៖
ជួរមានកំរិតដើមឈើដំបូង។
កម្ពស់កើនឡើងដូច្នេះកម្ពស់ = 1 ។
យកធាតុទាំងអស់នៃជួរហើយបន្ថែមកូន ៗ របស់ពួកគេចូលជួរ។
ជួរ = 7 -> 11

ផ្នែកទី ១៖
ជួរមានកម្រិតដើមឈើទីពីរ។
កម្ពស់កើនឡើងដូច្នេះកម្ពស់ = 2 ។
យកធាតុទាំងអស់នៃជួរហើយបន្ថែមកូន ៗ របស់ពួកគេចូលជួរ។
ជួរ = 5 -> 9 -> 3

ផ្នែកទី ១៖
ជួរមានកម្រិតដើមឈើទីបី។
កម្ពស់កើនឡើងដូច្នេះកម្ពស់ = 3 ។
យកធាតុទាំងអស់នៃជួរហើយបន្ថែមកូន ៗ របស់ពួកគេចូលជួរ។
ជួរ = គ្មាន

នៅពេលជួរក្លាយជាទទេដូច្នេះយើងឈប់នៅទីនេះ។

ជំហាន 5:

កម្ពស់ត្រឡប់មកវិញដូច្នេះកំពស់ដើមឈើគឺ 3 ។

លេខកូដ  

កូដចាវ៉ាសំរាប់វិធីសាស្រ្ត Iterative ដើម្បីស្វែងរកកំពស់ដើមឈើគោល

import java.util.LinkedList;
import java.util.Queue;

class IterativeMethodToFindHeightOfBinaryTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int height(Node root) {
        if (root == null) {
            return 0;
        }

        // create a queue and push root to it
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        // initialise height as 0
        int height = 0;

        // do a level order traversal
        // while queue is not empty
        while (!q.isEmpty()) {
            // increment height
            height++;
            // initialise size as size of queue
            int size = q.size();
            // Remove current level from queue and push next level
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = q.poll();
                // push current element's children to the queue
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
        }
        
        // return height
        return height;
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(2);
        root1.left = new Node(7);
        root1.right = new Node(11);
        root1.left.left = new Node(5);
        root1.right.left = new Node(9);
        root1.right.right = new Node(3);

        System.out.println(height(root1));

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);
        root2.left.left.left = new Node(7);
        root2.left.left.right = new Node(8);
        root2.right.right.left = new Node(9);
        root2.right.right.right = new Node(10);

        System.out.println(height(root2));
    }
}
3
4

លេខកូដ 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 height(Node *root) {
    if (root == NULL) {
        return 0;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialise height as 0
    int height = 0;
    
    // do a level order traversal
    // while queue is not empty
    while (!q.empty()) {
        // increment height
        height++;
        // initialise size as size of queue
        int size = q.size();
        // Remove current level from queue and push next level
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            // push current element's children to the queue
            q.pop();
            if (curr->left != NULL)
                q.push(curr->left);
            if (curr->right != NULL)
                q.push(curr->right);
        }
    }
    
    // return height
    return height;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(2);
    root1->left = newNode(7);
    root1->right = newNode(11);
    root1->left->left = newNode(5);
    root1->right->left = newNode(9);
    root1->right->right = newNode(3);

    cout<<height(root1)<<endl;

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);
    root2->left->left->left = newNode(7);
    root2->left->left->right = newNode(8);
    root2->right->right->left = newNode(9);
    root2->right->right->right = newNode(10);

    cout<<height(root2)<<endl;
    
    return 0;
}
3
4

ការវិភាគស្មុគស្មាញ  

ស្មុគស្មាញពេលវេលា

អូរ (n)ដែល n គឺជាចំនួនថ្នាំងនៅក្នុងមែកធាងគោលពីរ។ ចាប់តាំងពីយើងបានប្រើជួរហើយឆ្លងកាត់លើថ្នាំងទាំងអស់នៅក្នុងមែកធាងគោលពីរ។ ដូច្នេះវាច្បាស់ណាស់ថាពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

សូម​មើល​ផង​ដែរ
រៀបចំអារេឡើងវិញដែលមកដល់ [ខ្ញុំ] គឺស្មើនឹងខ្ញុំ

ភាពស្មុគស្មាញនៃលំហ

អូ (n), ដែល n ជាចំនួនថ្នាំងនៅក្នុងមែកធាងគោលពីរ។ ដូចដែលបានប្រាប់រួចហើយថាយើងបានប្រើជួរដើម្បីរកកំពស់យើងបានរក្សាទុកធាតុនៅក្នុងជួរនោះ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហរក៏ជាលីនេអ៊ែរដែរ។

ឯកសារយោង