បោះពុម្ពទិដ្ឋភាពខាងស្តាំនៃមែកធាងគោលពីរ


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

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

បញ្ហា“ បោះពុម្ពខាងស្តាំនៃមែកធាងគោលពីរ” បញ្ជាក់ថាអ្នកត្រូវបានគេអោយមែកធាងគោលពីរ។ ឥឡូវអ្នកត្រូវរកទិដ្ឋភាពត្រឹមត្រូវនៃដើមឈើនេះ។ នៅទីនេះទិដ្ឋភាពខាងស្ដាំនៃមែកធាងគោលពីរមានន័យថាបោះពុម្ពលំដាប់ដូចដើមឈើមើលនៅពេលមើលពីទិសដៅត្រឹមត្រូវ។

ឧទាហរណ៍

បោះពុម្ពទិដ្ឋភាពខាងស្តាំនៃមែកធាងគោលពីរ

2 7 4 6

ការពន្យល់

ប្រសិនបើអ្នកសង្កេតមើលដើមឈើគោលពីរក្នុងទិសដៅត្រឹមត្រូវ។ យើងអាចមើលឃើញតែថ្នាំងដែលត្រូវបានបោះពុម្ពនៅក្នុងលទ្ធផល។ ដោយសារតែថ្នាំងទី ៣ និងទី ៥ លាក់ខ្លួននៅពីក្រោយលេខ ៧ និង ៤ រៀងៗខ្លួន។

ខិតជិតដើម្បីបោះពុម្ពទិដ្ឋភាពត្រឹមត្រូវនៃមែកធាងគោលពីរ

នៅក្នុងបញ្ហានេះយើងត្រូវរកឱ្យឃើញនូវទិដ្ឋភាពខាងស្តាំ មែកធាងគោលពីរ។ បញ្ហាអាចត្រូវបានដោះស្រាយដោយប្រើវិធីសាស្រ្តពីរ។ មួយក្នុងចំណោមពួកគេប្រើជួរហើយមួយផ្សេងទៀតប្រើការហៅឡើងវិញ។ ដំបូងយើងនឹងពិភាក្សាវិធីសាស្រ្តដោយប្រើជួរ។ ដូច្នេះដើម្បីដោះស្រាយបញ្ហាដោយប្រើក ជួរ។ យើងចាប់ផ្តើមពីឫសនៃគោលពីរ។ សម្រាប់កម្រិតនីមួយៗនៃមែកធាងយើងបន្តរក្សាទុកថ្នាំងនៅក្នុងជួរ។ សម្រាប់ការរក្សាទុកថ្នាំងនៃកម្រិតបន្ទាប់យើងត្រូវឆ្លងកាត់ថ្នាំងនៃកម្រិតបច្ចុប្បន្ន។ ដូច្នេះនៅពេលដែលយើងកំពុងឆ្លងកាត់ថ្នាំងនៃកម្រិតបច្ចុប្បន្ន។ យើងបោះពុម្ពថ្នាំងចុងក្រោយនៅកម្រិតនេះ។ នៅពេលយើងសង្កេតមើលដើមឈើពីជ្រុងខាងស្តាំ។ ថ្នាំងតែមួយគត់ដែលអាចមើលឃើញសម្រាប់យើងគឺថ្នាំងខាងស្តាំនៅកម្រិតមួយ។ វិធីសាស្រ្តនេះប្រើជួរដែលចំណាយពេល។

ចូរពិភាក្សាអំពីដំណោះស្រាយដោយប្រើការហៅខ្លួនឯង។ ដំណោះស្រាយគឺប្រហាក់ប្រហែលនឹងការស្វែងរកទិដ្ឋភាពខាងឆ្វេងនៃដើមឈើ។ នៅក្នុងវិធីសាស្រ្តនេះ។ យើងគ្រាន់តែធ្វើត្រាប់តាមដើមឈើដែលផ្ទុយពីការឆ្លងដែលមិនមានលក្ខណៈ។ ប៉ុន្តែយើងក៏តាមដានកម្រិតដែលយើងកំពុងស្ថិតនៅនិងកម្រិតអតិបរមាដែលទទួលបានរហូតមកដល់បច្ចុប្បន្ន។ ដូចដែលយើងផ្លាស់ទៅអនុក្រិតខាងស្តាំមុនអនុក្រឹតខាងឆ្វេង។ នៅពេលណាដែលយើងចូលដល់កម្រិតថ្មីនៅក្នុងមែកធាង។ ដំបូងយើងជួបនឹងថ្នាំងខាងស្តាំបំផុត។ ដូច្នេះយើងតែងតែត្រួតពិនិត្យប្រសិនបើកម្រិតបច្ចុប្បន្នធំជាងកំរិតអតិបរមាយើងបោះពុម្ពថ្នាំង។ វិធីសាស្រ្តគឺល្អប្រសើរប្រសិនបើយើងមិនគិតពីទំហំដែលត្រូវការសម្រាប់ជង់អ្នកចងក្រង។ ភាពស្មុគស្មាញនៃលំហសម្រាប់បញ្ហាគឺពឹងផ្អែកទៅលើកំពស់ដើមឈើប្រសិនបើយើងពិចារណាលើលំហដែលយកដោយជង់ចងក្រង។

លេខកូដ

កូដ C ++ ដើម្បីបោះពុម្ពទិដ្ឋភាពខាងស្តាំនៃមែកធាងគោលពីរ

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

int main(){
  node *root = create(2);
  root->left = create(3);
  root->right = create(7);
  root->left->left = create(5);
  root->left->right =create(4);
  root->left->right->left = create(6);

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

កូដចាវ៉ាដើម្បីបោះពុម្ពទិដ្ឋិភាពនៃមែកធាងគោលពីរ

import java.util.*;

class node{
  int data;
  node left;
  node right;
}

class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  public static void main(String[] args){
    node root = create(2);
    root.left = create(3);
    root.right = create(7);
    root.left.left = create(5);
    root.left.right =create(4);
    root.left.right.left = create(6);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

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

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

O (N), យើងកំពុងឆ្លងកាត់ថ្នាំងនៅក្នុងមែកធាង។ ដូច្នេះប្រសិនបើមានថ្នាំង N នៅក្នុងដើមឈើនោះក្បួនដោះស្រាយតម្រូវឱ្យមានប្រតិបត្ដិការ O (N) ។

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

ឱ (១) ។ ប្រសិនបើចន្លោះប្រើដោយជង់អ្នកចងក្រងមិនត្រូវបានពិចារណាទេ O (H) ត្រូវការកន្លែងទំនេរ។