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


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

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

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

ឧទាហរណ៍

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

2nd ancestor of 4 is 7

វិធីសាស្រ្ត

បញ្ហាស្នើឱ្យបោះពុម្ពជីដូនជីតាតនៃថ្នាំងដែលបានផ្តល់ឱ្យ។ បុព្វបុរសគឺគ្មានអ្វីក្រៅពីថ្នាំងដែលចូលមកតាមផ្លូវនៃថ្នាំងពីឫស។ មេនៃថ្នាំងក៏ជាបុព្វបុរសរបស់វាដែរ។

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

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

វិធីសាស្រ្តដូចគ្នាត្រូវបានប្រើនៅក្នុងឯកសារ អ្នកស្នងរាជ្យបន្តបន្ទាប់នៃដើមគោលពីរ.

លេខកូដ

លេខកូដ 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* tmp = NULL;

node* kthAncestor(node *root, int cur, int &k)
{
  if (root == NULL)
    return NULL;
  if (root->data == cur || (tmp = kthAncestor(root->left,cur,k)) || (tmp = kthAncestor(root->right,cur,k))){
    if(k)k--;
    else if (k == 0){
      cout<<"kth ancestor of "<<cur<<" is "<<root->data;
      return NULL;
    }
    return root;
  }
}

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);
  int k = 2;
  kthAncestor(root, 4, k);
}
kth ancestor of 4 is 7

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

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 int k = 2;
  static node tmp = null;

  static node kthAncestor(node root, int cur)
  {
    if (root == null)
      return null;
    if ((root.data == cur) || ((tmp = kthAncestor(root.left,cur)) != null) || ((tmp = kthAncestor(root.right,cur)) != null)){
      if(k > 0)k--;
      else if (k == 0){
        System.out.print("kth ancestor of "+cur+" is "+root.data);
        return null;
      }
      return root;
    }
    return null;
  }

  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);
    k = 2;
    kthAncestor(root, 4);
  }
}
kth ancestor of 4 is 7

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

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

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

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

O (N)ពីព្រោះជង់ចងក្រងដែលត្រូវបានប្រើសម្រាប់មុខងារហៅវិញ។