बायनरी ट्रीमधील नोडचे पूर्वज कॅथ


अडचण पातळी हार्ड
वारंवार विचारले ऍमेझॉन Google
बायनरी ट्री झाड ट्री ट्रॅव्हर्सल

समस्या विधान

“बायनरी ट्रीमधील नोडचा Kth पूर्वज” ही समस्या सांगते की आपल्याला ए बायनरी ट्री आणि एक नोड आता आपल्याला या नोडचा kth पूर्वज शोधण्याची आवश्यकता आहे. कोणत्याही नोडचा पूर्वज नोड असतो जो मूळपासून ते नोडच्या पालकांपर्यंतच्या मार्गावर पडतो.

उदाहरण

बायनरी ट्रीमधील नोडचे पूर्वज कॅथ

2nd ancestor of 4 is 7

दृष्टीकोन

दिलेल्या नोडचा kth पूर्वज मुद्रित करण्यास समस्या विचारते. पूर्वज नोड्सशिवाय काही नसतात जे मुळातून नोडच्या मार्गावर येतात. नोडचे पालक देखील त्याचे पूर्वज असतात.

एक सोपा आणि सोपा उपाय म्हणजे वापर BFS. हे समाधान सोपे आणि कार्यक्षम देखील आहे परंतु प्रथम आपण प्रत्येक नोडचे पालक झाडामध्ये साठवले पाहिजेत. मग अडचण फक्त ट्री के अंतरावर हलविण्यासाठी खाली उकळते. त्याऐवजी नोड्सच्या मुलांना ढकलण्याऐवजी. आम्ही फक्त प्रत्येक नोडच्या पालकांना धक्का देऊ.

परंतु या सोल्यूशनमध्ये, वर चर्चा केलेल्या दृष्टिकोनाऐवजी. आम्ही एक वापरू डीएफएस आधारित दृष्टीकोन डीएफएस आधारित दृष्टिकोनात आम्ही बॅकट्रॅकिंगचा फायदा घेत आहोत. एकदा आम्हाला झाडावर नोड सापडला की रिकर्सिव्ह फंक्शनकडे परत जाते ज्याला या रिकर्सिव फंक्शन म्हटले जाते. म्हणून जेव्हा आपण के पावले मागे सरकतो, तेव्हा आम्ही स्तरावर नोड मुद्रित करतो. कारण ते आमचे 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण सर्वात वाईट परिस्थितीत आम्हाला आवश्यक नोड शोधण्यापूर्वी सर्व नोड्सला जावे लागू शकतात.

स्पेस कॉम्प्लेक्सिटी

ओ (एन)कंपाइलर स्टॅकमुळे जे रिकर्सिव्ह फंक्शन्ससाठी वापरले जात आहे.