ការផ្លាស់ប្តូរការបញ្ជាទិញជាមុន


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន google ដោយឡែកក្រុមហ៊ុន JP Morgan ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley Uber
មែកធាង ការឆ្លងកាត់ដើមឈើ

បញ្ហា“ ភាពទាក់ទាញនៃការបញ្ជាទិញជាមុន” បញ្ជាក់ថាអ្នកត្រូវបានគេផ្តល់ឱ្យនូវគោលពីរហើយឥឡូវអ្នកត្រូវរកវា ឆ្លងកាត់ការបញ្ជាទិញជាមុន នៃមែកធាង។ យើងតំរូវអោយរកវិធីផ្លាស់ប្តូរការបញ្ជាទិញជាមុនដោយប្រើវិធីដដែលៗហើយមិនមែនវិធីសាស្រ្តដែលហៅខ្លួនឯងមកទេ។

ឧទាហរណ៍

ការផ្លាស់ប្តូរការបញ្ជាទិញជាមុន

 

5 7 9 6 1 4 3

វិធីសាស្រ្តក្នុងការបោះពុម្ព

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

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

លេខកូដ

លេខកូដ C ++ ដើម្បីបោះពុម្ព Traversal Iterative Preorder Traversal

#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 preorder(node* root){
    // create a stack
    stack<node*> s;

    while(root){
        // print the current node
        cout<<root->data<<" ";
        
        // if current node has right sub-tree
        // then store it and use it afterwards
        if(root->right)
            s.push(root->right);
        // now move to left child of current node
        // if the left child does not exists 
        // then in the next condition we will move up in the tree
        // and assign the right children which 
        // we have been storing the stack
        root = root->left;
        if(!root && !s.empty()){
                root = s.top(), s.pop();
        }
    }
}

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

  preorder(root);
}
5 7 9 6 1 4 3

កូដចាវ៉ាដើម្បីបោះពុម្ពការត្រាស់ដឹងជាមុន

import java.util.*;

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

class Main{

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

  static void preorder(node root){
      // create a stack
      Stack<node> s = new Stack<node>();

      while(root != null){
          // print the current node
          System.out.print(root.data+" ");

          // if current node has right sub-tree
          // then store it and use it afterwards
          if(root.right != null)
              s.add(root.right);
          // now move to left child of current node
          // if the left child does not exists
          // then in the next condition we will move up in the tree
          // and assign the right children which
          // we have been storing the stack
          root = root.left;
          if(root == null && !s.empty()){
                  root = s.peek();
                  s.pop();
          }
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    preorder(root);
  }
}
5 7 9 6 1 4 3

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

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

O (N), ចាប់តាំងពីយើងបានឆ្លងកាត់ធាតុទាំងអស់នៃដើមឈើ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

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

O (H), ក្នុងករណីអាក្រក់បំផុតថ្នាំងនីមួយៗអាចមានកូនត្រឹមត្រូវ។ ដោយសារតែយើងកំពុងរក្សាទុកកូនខាងស្តាំនៃថ្នាំងនីមួយៗនៅក្នុងផ្លូវឆ្ពោះទៅកូនខាងឆ្វេង។ ដូច្នេះយើងអាចផ្ទុកនៅថ្នាំងអតិបរិមា (អ៉) នៅក្នុងជង់។