દ્વિસંગી વૃક્ષમાં નોડના પૂર્વક Kth


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન Google
દ્વિસંગી વૃક્ષ વૃક્ષ વૃક્ષ આડેધડ

સમસ્યા નિવેદન

સમસ્યા "બાઈનરી ટ્રીમાં નોડના Kth પૂર્વજો" જણાવે છે કે તમને એ દ્વિસંગી વૃક્ષ અને નોડ હવે આપણે આ નોડના kth પૂર્વજ શોધવાની જરૂર છે. કોઈપણ નોડના પૂર્વજ એ નોડ્સ છે જે મૂળમાંથી નોડના પિતૃ તરફના માર્ગ પર આવેલા છે.

ઉદાહરણ

દ્વિસંગી વૃક્ષમાં નોડના પૂર્વક Kth

2nd ancestor of 4 is 7

અભિગમ

સમસ્યા આપેલ નોડના kth પૂર્વજને છાપવા માટે પૂછે છે. પૂર્વજ એ નોડ સિવાય બીજું કંઈ નથી જે મૂળમાંથી નોડના માર્ગમાં આવે છે. નોડના માતાપિતા પણ તેના પૂર્વજ છે.

એક સરળ અને સરળ ઉપાય એ ઉપયોગ કરવો છે બીએફએસ. આ સોલ્યુશન સરળ અને કાર્યક્ષમ પણ છે પરંતુ અમને દરેક નોડના પેરેન્ટ્સને ઝાડમાં સંગ્રહિત કરવાની જરૂર છે. તો પછી સમસ્યા ફક્ત વૃક્ષની અંતરમાં આગળ વધવા માટે ઉકળે છે. તેથી ગાંઠોના બાળકોને દબાણ કરવાને બદલે. અમે ફક્ત દરેક નોડના માતાપિતાને દબાણ કરીશું.

પરંતુ આ ઉકેલમાં ઉપર જણાવેલ અભિગમ સાથે જવાને બદલે. અમે ઉપયોગ કરીશું DFS આધારિત અભિગમ ડીએફએસ આધારિત અભિગમમાં, અમે બેકટ્રેકિંગનો લાભ લઈ રહ્યા છીએ. એકવાર અમને ઝાડમાં નોડ મળી જાય, ફરી વળવું તે ફંક્શનમાં ફરી રહ્યું છે જેને આ રિકર્સીવ ફંક્શન કહે છે. તેથી જ્યારે આપણે 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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે સૌથી ખરાબ કિસ્સામાં, બધા ગાંઠો પસાર કરવા પડી શકે છે, જે પહેલાં અમને જરૂરી નોડ મળે છે.

અવકાશ જટિલતા

ઓ (એન), કમ્પાઇલર સ્ટેકને લીધે જે પુનરાવર્તિત કાર્યો માટે વપરાય છે.