मैं एक बाइनरी खोज पेड़ में नोड के nth पूर्वजों को कैसे ढूंढूं?

Question

मुझे नौकरी साक्षात्कार में यह पूछा गया। यहां मेरा O(log n) समाधान है।

नोड की गहराई पाएं। खोज दोहराएं, लेकिन depth - n पर रुकें।

क्या दूसरे पास के बिना ऐसा करने का कोई तरीका है?

Answer 1

नोड के लिए अपनी खोज में आप वर्तमान नोड से रूट में सभी नोड्स का ट्रैक रख सकते हैं। यह एक साधारण सूची है जिसमें वृक्ष की गहराई से अधिक लंबाई नहीं है। एक बार नोड पाया गया है, इसकी एन वें पूर्वजों की सूची में लंबाई - एन स्थिति पर है।

Answer 2

बस नोड की तलाश करें और जिस मार्ग का आप अनुसरण करते हैं उसे सहेजें। मोटे तौर पर यह (ints की एक पेड़ के लिए):

Node* nthAncestor(Node* root, int target, int n) 
{ 
    Node* list[n]; 
    int pos = 0; 
    Node* node = root; 
    while(node->value != target) 
    { 
     list[pos] = node; 
     pos = (pos + 1) % n; 
     if(node->value < target) 
      node = node->left; 
     else if(node->value > target) 
      node = node->right; 
    } 

    return list[(pos + 1) % n]; 
} 

कृपया ध्यान दें कि मैं वें पूर्वज मौजूद है ग्रहण किया।

आकार टी के एक पेड़ इस O(log T) समय में चलाता है और ( n वें पूर्वज के रूप में n) O(n) स्थान का उपयोग करता लिए

।

Answer 3

आपका प्रश्न थोड़ा गलत है, मुझे लगता है। आप एक महत्वपूर्ण बात याद करते हैं। बेशक आप इसे दूसरे पास के बिना कर सकते हैं। अपनी खोज में अंतिम एन नोड्स के queue को बनाए रखें।

आपको क्या याद आती है कि इस तरह के एल्गोरिदम को O(log n) मेमोरी की आवश्यकता है। जबकि आपका समाधान स्मृति उपयोग के लिए समय खपत का व्यापार करता है, और O(1) (अतिरिक्त राशि) अतिरिक्त मेमोरी का उपयोग करता है)

तो आपका समाधान "गलत" या "बहुत धीमा" नहीं है। यह सिर्फ अपने पेशेवरों और विपक्ष है।

Answer 4

हम्म, यह मुझे लगता है कि एक आसान तरीका है जिसके लिए केवल एक अतिरिक्त नोड या अंतरिक्ष में कम आवश्यकता होती है, जिसमें एक डमी नोड होता है जो बैकट्रैक गिनती रखता है। जब आप खोज लक्ष्य पाते हैं, तो आप डमी नोड को n पर सेट करें और इसे पर वापस न करें, न कि जिस नोड को आप नहीं चाहते हैं।

आपको एक फ़ंक्शन DUMMY(node) की आवश्यकता है जो केवल डमी नोड के लिए सत्य लौटाता है। (DUMMY() नोड पते की तुलना द्वारा या नोड के अंदर एक जादू कुकी के लिए जाँच के द्वारा लागू किया जा सकता है।)

Node *search(Node *next) { 
    if (found the the answer) 
    dummy->backtrack = n; 
    return dummy; 
    } else r = search(whatever ? n->left : n->right); 
    if (DUMMY(r)) { 
    if (dummy->backtrack == 0) 
     return next; 
    --dummy->backtrack; 
    } 
    return r; 
} 

Answer 5

इस के लिए एक n स्थान दिया गया है कतार का प्रयोग करें। जब भी आपको एक, डेक और एनक्यू मिल जाए,

findnth(node *root, queue q, int n, int number) 
{ 
    if(!root || !q) 
     return; 
    findnth(root->left, q, n, number); 
    if(root->d == number) { 
     if(q.size() < n) { 
     nth ancestor not exist; 
     print q->deq() as q.size() ance return; 
     } 
     else 
     print q.deq() 
    } 
    if(q.size() < n) { 
     q.ins(node->data); 
    } 
    else { 
     q.deq();q.enq(node->data); 
    } 
    findnth(root->right, q, n, number); 
} 

Answer 6

हाँ यह दूसरे पास के बिना किया जा सकता है। आपको बस दो पॉइंटर्स का उपयोग करने की आवश्यकता है। यहाँ कैसे आप इसे

1. कर सकते हैं एक सूचक p1 का उपयोग करना, जड़ से शुरू नोड जिसका पूर्वज पाया जा सकता है के लिए खोज है। लेकिन आप केवल n कदम नीचे जाते हैं।
2. अब जब आप एन चरणों तक पहुंचते हैं, तो रूट से एक और पॉइंटर पी 2 शुरू करें, जो एक ही नोड की खोज करता है।
3. लॉक चरण में दोनों पॉइंटर्स को ले जाएं, जैसे कि वे दोनों एक स्तर को एक साथ नीचे जाते हैं। जब पी 1 आपके नोड तक पहुंचता है, तो पी 2 एनएच पूर्वजों पर इंगित करेगा।

Answer 7

I think this function might help ... 

function printAncestor(node *root , node *search , int *k) 
{ 
    if(!root) 
    return 0; 
    if(root == search) 
    return 1; 

    int p1 ,p2; 
    p1 = printAncestor(root->left , search , k); 
    p2 = printAncestor(root->right , search , k); 

if(p1) { 
    (*k)--; 
if(*k >0) 
    printf("%d ",root->left->value); 
return 1; 
} 
if(p2) 
{ 
    (*k)--; 
    if(*k >0) 
    printf("%d ",root->right->value); 
return 1; 
} 
} 

इसके पीछे तर्क यह है कि, हम recursion.When के माध्यम से जड़ हम उसे ढूंढने से खोज नोड तक जाना है, तो हम रास्ता है कि यह से आया है और इसे प्रिंट के साथ बढ़ावा देते हैं।