यह पोस्ट एक बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल के बारे में है, ट्री को ट्रैवर्स करने की एक विधि जिसमें वर्तमान नोड को उसके बच्चों से पहले देखा जाता है। प्रीऑर्डर ट्रैवर्सल एल्गोरिथ्म पहले रूट नोड पर जाता है, फिर पुनरावर्ती रूप से बाएं सबट्री पर जाता है, उसके बाद राइट सबट्री पर जाता है। प्रीऑर्डर ट्रैवर्सल का नतीजा नोड्स के मूल्यों की एक सूची है जिस क्रम में वे देखे गए हैं। यह पोस्ट आपको यह समझने में मदद करेगी कि बाइनरी ट्री को कैसे पार करना है और इसे विभिन्न तरीकों से कैसे लागू करना है।
प्रीऑर्डर ट्रैवर्सल एक बाइनरी ट्री को पार करने की एक विधि है जहां वर्तमान नोड को उसके बच्चों से पहले देखा जाता है। एल्गोरिथ्म पहले रूट नोड पर जाता है, फिर पुनरावर्ती रूप से बाएं सबट्री पर जाता है, उसके बाद राइट सबट्री। प्रीऑर्डर ट्रैवर्सल का नतीजा नोड्स के मूल्यों की एक सूची है जिस क्रम में वे देखे गए हैं।
इस समस्या में, आपको कोटलिन में TreeNode वर्ग द्वारा दर्शाए गए एक बाइनरी ट्री की जड़ दी गई है, जिसमें नोड के मान के लिए एक val गुण है और इसके बाएँ और दाएँ बच्चों के लिए क्रमशः left और right गुण हैं। आपका कार्य एक फ़ंक्शन के दो कार्यान्वयनों को लिखना है जो बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल निष्पादित करता है और नोड्स के मानों की सूची लौटाता है। एक पुनरावर्ती समाधान होना चाहिए और दूसरा पुनरावृत्ति का उपयोग नहीं करना चाहिए।
यहाँ समारोह का वर्ग हस्ताक्षर है:
fun preorderTraversal(root: TreeNode?): List<Int>
फ़ंक्शन का इनपुट बाइनरी ट्री का रूट नोड है, और आउटपुट पूर्णांकों की एक सूची है जो नोड्स के मूल्यों का प्रतिनिधित्व करते हैं, जिस क्रम में वे प्रीऑर्डर ट्रैवर्सल के दौरान देखे जाते हैं।
विवरण:
एक बाइनरी ट्री की जड़ को देखते हुए, इसके नोड्स के मानों का प्रीऑर्डर ट्रैवर्सल लौटाएं। इसे एक पुनरावर्ती समाधान के साथ और पुनरावर्तन का उपयोग किए बिना करें।
class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }
यहाँ समस्या का एक पुनरावर्ती समाधान है:
fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }
यह फ़ंक्शन बाइनरी ट्री का एक प्रीऑर्डर ट्रैवर्सल करता है और नोड्स के मानों की सूची उस क्रम में लौटाता है जिस क्रम में वे देखे गए हैं।
यह एल्गोरिथ्म इस प्रकार काम करता है:
- यदि रूट नोड खाली है, तो एक खाली सूची लौटाएं।
- परिणाम सूची में रूट नोड का मान जोड़ें।
- रूट के बाएँ बच्चे पर फ़ंक्शन को कॉल करके बाएं सबट्री को फिर से पार करें और परिणाम सूची में लौटी हुई सूची जोड़ें।
- रूट के दाहिने बच्चे पर फ़ंक्शन को कॉल करके सही सबट्री को फिर से पार करें और परिणाम सूची में लौटी हुई सूची जोड़ें।
- परिणाम सूची वापस करें।
इस एल्गोरिथ्म में O(n) की समय जटिलता है, जहाँ n पेड़ में नोड्स की संख्या है, और O(h) की एक अंतरिक्ष जटिलता है, जहाँ h पेड़ की ऊँचाई है (कॉल स्टैक के कारण)।
यहाँ एक पुनरावृत्त दृष्टिकोण का उपयोग करके एक समाधान है (यानी, पुनरावर्तन का उपयोग किए बिना):
fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }
यह फ़ंक्शन बाइनरी ट्री का एक प्रीऑर्डर ट्रैवर्सल करता है और नोड्स के मानों की सूची उस क्रम में लौटाता है जिस क्रम में वे देखे गए हैं। यह उन नोड्स का ट्रैक रखने के लिए स्टैक का उपयोग करता है जिन्हें अभी भी देखने की आवश्यकता है।
यह एल्गोरिथ्म इस प्रकार काम करता है:
एक खाली ढेर को प्रारंभ करें और वर्तमान नोड को पेड़ की जड़ पर सेट करें।
जबकि वर्तमान नोड शून्य नहीं है या ढेर खाली नहीं है:
जबकि वर्तमान नोड शून्य नहीं है:
- परिणाम सूची में वर्तमान नोड का मान जोड़ें।
- स्टैक पर वर्तमान नोड को पुश करें।
- वर्तमान नोड को उसके बाएं बच्चे पर सेट करें।
शीर्ष नोड को स्टैक से पॉप करें और वर्तमान नोड को उसके दाहिने बच्चे पर सेट करें।
परिणाम सूची वापस करें।
इस एल्गोरिथम की समय जटिलता O(n) है, जहां n पेड़ में नोड्स की संख्या है, और O(h) की अंतरिक्ष जटिलता है, जहां h पेड़ की ऊंचाई है।
आशा है यह मदद करेगा! अगर आपके पास कोई अन्य सवाल है तो मुझे बताएं।
