អ្នកស្នងបន្តនៃថ្នាំងនៅក្នុងមែកធាងប្រព័ន្ធគោលពីរ


កម្រិតលំបាក រឹង
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Expedia ក្រុមហ៊ុន Morgan Stanley បន្ទប់អូយ Snapchat
មែកធាងស្វែងរកគោលពីរ មែកធាង

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

បញ្ហាសួររក“ អ្នកស្នងដំណែងនៃថ្នាំងនៅក្នុងមែកធាងគោលពីរ” ។ អ្នកស្នងបន្តនៃថ្នាំងគឺជាថ្នាំងមួយនៅក្នុងមែកធាងគោលពីរដែលកើតឡើងបន្ទាប់ពីថ្នាំងដែលបានផ្តល់ឱ្យនៅក្នុងការផ្លាស់ប្តូរអេកូនៃដើមឈើគោលពីរដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍

Inorder successor of 6 is 4

ការពន្យល់

ការផ្លាស់ប្តូរនៃដើមឈើគឺពី ៩ ៧ ១ ៦ ៤ ៥ ៣ ។ ដូច្នេះអ្នកស្នងរាជ្យពី ១ គឺ ៦ ។

វិធីសាស្រ្ត

ជាទូទៅយើងត្រូវបានគេប្រាប់ឱ្យរកថ្នាំងបន្ទាប់នៅក្នុងការឆ្លងកាត់នៃអ៊ី មែកធាងស្វែងរកគោលពីរ។ ប៉ុន្តែវាខុសពីដើមឈើគោលពីរ។ ដូច្នេះរឿងមួយដែលយើងគួរកត់សំគាល់នោះគឺការផ្លាស់ប្តូរនៃដើមគោលពីរទូទៅដែលមិនមានលំដាប់លំដោយ។ ឥឡូវចូរយើងបន្តដំណើរទៅមុខទៀត។ ដូច្នេះប្រសិនបើយើងមានថ្នាំងបន្ទាប់មកមាន ៣ ករណីដែលយើងគួរតែមើល។

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

ឥឡូវនេះករណីចុងក្រោយគឺប្រសិនបើថ្នាំងគឺជាកូនដែលត្រឹមត្រូវបំផុត។ ប្រសិនបើវាកើតឡើងវាមិនមានអ្នកស្នងអ៊ីណុកសម្រាប់ថ្នាំងទេ។

លេខកូដ

កូដ 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;
}

node* findLeftMostNode(node* root){
  while(root && root->left) root = root->left;
  return root;
}

node* findRightMostNode(node* root){
  while(root && root->right) root = root->right;
  return root;
}

node* findAncestorSuccessor(node* root, node* given)
{
  if(root){
    if(root == given)
      return root;
    node* tmp = findAncestorSuccessor(root->left, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
    tmp = findAncestorSuccessor(root->right, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
  }
    return NULL;
}

void findInorderSuccesor(node* root, node* given)
{
    // if right child exists
    if(given->right)
    {
    	node* leftmost = findLeftMostNode(given);
    	cout<<"Inorder Succesor of "<<given->data<<" is "<<leftmost->data;
    	return;
    }
    // if right child does not exists
    if(given->right == NULL)
    {
        node* rightmost = findRightMostNode(root);
        if(rightmost == given)
            cout<<"Inorder Successor does not exists";
        else
        	findAncestorSuccessor(root, given);
    }
}

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);
  findInorderSuccesor(root, root->left->right->left);
}
Inorder Successor of 1 is 6

កូដចាវ៉ាដើម្បីរកអ្នកស្នងបន្តនៃថ្នាំងមួយនៅក្នុងមែកធាងប្រព័ន្ធគោលពីរ

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 node findLeftMostNode(node root){
    while(root != null && root.left != null) root = root.left;
    return root;
  }

  static node findRightMostNode(node root){
    while(root != null && root.right != null) root = root.right;
    return root;
  }

  static node findAncestorSuccessor(node root, node given)
  {
    if(root != null){
      if(root == given)
        return root;
      node tmp = findAncestorSuccessor(root.left, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
      tmp = findAncestorSuccessor(root.right, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
    }
      return null;
  }

  static void findInorderSuccesor(node root, node given)
  {
      // if right child exists
      if(given.right != null)
      {
      	node leftmost = findLeftMostNode(given);
      	System.out.print("Inorder Successor of "+given.data+" is "+leftmost.data);
      	return;
      }
      // if right child does not exists
      else
      {
          node rightmost = findRightMostNode(root);
          if(rightmost == given)
              System.out.print("Inorder Successor does not exists");
          else
          	findAncestorSuccessor(root, given);
      }
  }

  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);
    findInorderSuccesor(root, root.left.right.left);
  }
}
Inorder Successor of 1 is 6

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

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

O (N) ពីព្រោះក្នុងករណីដ៏អាក្រក់បំផុតយើងប្រហែលជាត្រូវឆ្លងកាត់ថ្នាំងទាំងអស់។

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

អូ (H), ចាប់តាំងពីយើងបានប្រើការហៅឡើងវិញ។ ដូច្នេះប្រសិនបើយើងពិចារណាលើទំហំដែលយកដោយជង់អ្នកចងក្រង។ ភាពស្មុគស្មាញនៃលំហគឺពឹងផ្អែកលើកម្ពស់ដើមឈើ។