बाइनरी वृक्ष का इन-ऑर्डर ट्रेवर्सल
बाइनरी वृक्ष का इन-ऑर्डर ट्रेवर्सल एक पुनरावर्ती (recursive) प्रक्रिया है, जिसमें पहले किसी नोड के बाएँ उपवृक्ष को देखा जाता है, उसके बाद उस नोड को, और फिर उसके दाएँ उपवृक्ष को:
बाएँ उपवृक्ष (
node.left) पर जाएँवर्तमान नोड पर जाएँ
दाएँ उपवृक्ष (
node.right) पर जाएँ
यह कुछ ऐसा है मानो पूरे बाइनरी वृक्ष को रूट से लटका दिया गया हो और फिर उसके मानों को बाएँ से दाएँ क्रम में पढ़ा जा रहा हो।
दिए गए बाइनरी वृक्ष पर आपको इन-ऑर्डर ट्रेवर्सल करने के लिए कहा गया है।
इनपुट
इनपुट में स्पेस-सेपरेटेड इन्टीजर दिए होते हैं, जो बाइनरी वृक्ष में नोड्स के मान को दर्शाते हैं। मानों की क्रमबद्धता इस तरह है कि बाएँ उपवृक्ष से दाएँ उपवृक्ष की तरफ़ बढ़ते समय जो मान मिलते हैं, उन्हें उसी क्रम में इनपुट किया गया है। किसी नोड के लिए 0 का अर्थ होता है कि वह नोड मौजूद नहीं है। यह सुनिश्चित है कि इनपुट के रूप में दिया गया बाइनरी वृक्ष मान्य है।
आउटपुट
प्रोग्राम को बाइनरी वृक्ष के नोड्स की इन-ऑर्डर ट्रेवर्सल से प्राप्त मानों को प्रिंट करना चाहिए। सभी मानों को स्पेस से अलग किया जाना चाहिए।
उदाहरण
Input | Output |
|---|---|
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 4 9 2 5 1 6 3 7 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 2 5 1 6 3 7 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 2 5 1 6 3 8 7 9 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 2 7 5 8 1 3 6 |
व्याख्या
Example 1:
Example 2:
Example 3:
Example 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB