अगर 2 चेक पेड़ नोड्स से संबंधित हैं (यानी पूर्वज-वंशज) के साथअगर 2 चेक पेड़ नोड्स हे में (पूर्वज/वंशज) से संबंधित हैं (1) पूर्व प्रसंस्करण
- हे में इसे हल (1) समय के साथ हे (एन) अंतरिक्ष (N = नोड्स के #)
- पूर्व प्रसंस्करण की अनुमति दी है
यह है कि। मैं नीचे अपने समाधान (दृष्टिकोण) जा रहा हूँ। अगर आप खुद को पहले सोचना चाहते हैं तो कृपया रोकें।
एक पूर्व प्रसंस्करण के लिए मैं एक पूर्व आदेश (रिकर्सिवली पहले जड़ के माध्यम से जाना बच्चों तब,) और प्रत्येक नोड के लिए एक लेबल देते हैं का फैसला किया।
मुझे विवरण में लेबल समझाएं। प्रत्येक लेबल में अल्पविराम से अलग प्राकृतिक संख्याएं शामिल होंगी जैसे "1,2,1,4,5" - इस अनुक्रम की लंबाई (नोड + 1 की गहराई) के बराबर होती है। जैसे रूट का लेबल "1" है, रूट के बच्चों के लेबल "1,1", "1,2", "1,3" आदि होंगे .. अगला-स्तरीय नोड्स में "1,1,1" लेबल होंगे , "1,1,2", ..., "1,2,1", "1,2,2", ...
मान लें कि "ऑर्डर संख्या" नोड का है "इस नोड की 1-आधारित इंडेक्स" अपने माता-पिता की बच्चों की सूची में।
सामान्य नियम: नोड के लेबल में इसके माता-पिता के लेबल होते हैं और इसके बाद कॉम और "ऑर्डर संख्या" नोड का होता है।
इस प्रकार, जवाब देने के लिए दो नोड्स हे (1) में संबंधित हैं अगर (अर्थात पूर्वज-वंशज), मैं जाँच करेंगे, तो उनमें से एक का लेबल "एक उपसर्ग" के अन्य लेबल की है। हालांकि मुझे यकीन नहीं है कि ऐसे लेबलों को ओ (एन) अंतरिक्ष पर कब्जा करने के लिए माना जा सकता है।
फिक्सेस या वैकल्पिक दृष्टिकोण वाले किसी भी आलोचकों की अपेक्षा की जाती है।
ओएस (एन^2) अंतरिक्ष सबसे बुरी स्थिति परिदृश्य में है जिसमें प्रत्येक नोड में एक बच्चा (नूडल) होता है। – WeaselFox