பைனரி மரத்தில் ஒரு முனையின் Kth மூதாதையர்  


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அமேசான் கூகிள்
பைனரி மரம் மரம் மரம் பயணம்

சிக்கல் அறிக்கை  

"பைனரி மரத்தில் ஒரு முனையின் Kth மூதாதையர்" என்ற சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது பைனரி மரம் மற்றும் ஒரு முனை. இப்போது நாம் இந்த முனையின் kth மூதாதையரைக் கண்டுபிடிக்க வேண்டும். எந்த முனையின் மூதாதையரும் வேரிலிருந்து முனையின் பெற்றோர் செல்லும் பாதையில் அமைந்திருக்கும் முனைகளாகும்.

உதாரணமாக  

பைனரி மரத்தில் ஒரு முனையின் Kth மூதாதையர்முள்  

2nd ancestor of 4 is 7

அணுகுமுறை  

கொடுக்கப்பட்ட முனையின் kth மூதாதையரை அச்சிட சிக்கல் கேட்கிறது. ஒரு மூதாதையர் வேரிலிருந்து முனையின் பாதையில் வரும் முனைகளைத் தவிர வேறில்லை. ஒரு முனையின் பெற்றோரும் அதன் மூதாதையர்.

ஒரு எளிய மற்றும் எளிதான தீர்வு பயன்படுத்த வேண்டும் பிஎஃப்எஸ்ஸின். இந்த தீர்வு எளிதானது மற்றும் திறமையானது, ஆனால் முதலில் ஒவ்வொரு முனையின் பெற்றோரையும் மரத்தில் சேமிக்க வேண்டும். மரம் k தூரத்தில் மேலே செல்ல சிக்கல் வெறுமனே கொதிக்கிறது. எனவே முனைகளின் குழந்தைகளைத் தள்ளுவதற்குப் பதிலாக. ஒவ்வொரு முனையின் பெற்றோரையும் மட்டுமே தள்ளுவோம்.

ஆனால் இந்த தீர்வில், மேலே விவாதிக்கப்பட்ட அணுகுமுறையுடன் செல்வதற்கு பதிலாக. நாம் ஒரு பயன்படுத்துவோம் உண்மை கண்டறியும் அடிப்படையிலான அணுகுமுறை. டி.எஃப்.எஸ் அடிப்படையிலான அணுகுமுறையில், நாங்கள் பின்வாங்கலைப் பயன்படுத்துகிறோம். மரத்தில் முனையைக் கண்டறிந்ததும், மறுநிகழ்வு இந்த சுழல்நிலை செயல்பாடு என்று அழைக்கப்படும் செயல்பாட்டுக்குத் திரும்பிச் செல்கிறது. எனவே நாம் k படிகளை பின்னால் நகர்த்தும்போது, ​​முனையை மட்டத்தில் அச்சிடுகிறோம். ஏனென்றால் அது எங்கள் kth மூதாதையர் மற்றும் பூஜ்யமாக திரும்பும்.

மேலும் காண்க
பைனரி மரத்தில் அதிகபட்ச நிலை தொகையைக் கண்டறியவும்

அதே அணுகுமுறை பயன்படுத்தப்படுகிறது பைனரி மரத்தின் ஒழுங்கற்ற வாரிசு.

குறியீடு  

பைனரி மரத்தில் ஒரு முனையின் Kth மூதாதையரைக் கண்டுபிடிக்க சி ++ குறியீடு

#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

பைனரி மரத்தில் ஒரு முனையின் Kth மூதாதையரைக் கண்டுபிடிக்க ஜாவா குறியீடு

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

சிக்கலான பகுப்பாய்வு  

நேர சிக்கலானது

ஓ (என்), ஏனெனில் மோசமான நிலையில் தேவையான முனைகளைக் கண்டுபிடிக்கும் அனைத்து முனைகளையும் கடந்து செல்ல வேண்டியிருக்கும்.

மேலும் காண்க
நிகழும் அதிகபட்ச எழுத்து

விண்வெளி சிக்கலானது

ஓ (என்), கம்பைலர் ஸ்டேக் காரணமாக இது சுழல்நிலை செயல்பாடுகளுக்கு பயன்படுத்தப்படுகிறது.