Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में दिशाओं की सूची का उपयोग करके बाइनरी ट्री को पार करने का प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी ट्री और moves नामक स्ट्रिंग्स की एक सूची है जिसमें "R" (दाएं), "L" (बाएं) और "U" (ऊपर) शामिल हैं। रूट से शुरू करके, हमें moves में प्रत्येक चाल को निष्पादित करके ट्री को पार करना होगा जहां: "R" दाएं चाइल्ड को पार करने का संकेत देता है। "L" बाएं चाइल्ड को पार करने का संकेत देता है। "U" उसके पैरेंट को पार करने का संकेत देता है।

तो, यदि इनपुट इस तरह है

Python में दिशाओं की सूची का उपयोग करके बाइनरी ट्री को पार करने का प्रोग्राम

["R","R","U","L"], तो आउटपुट 3 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

  • past := एक नई सूची
  • moves में प्रत्येक चाल के लिए, करें
    • root को past के अंत में डालें
    • यदि चाल "L" के समान है, तो root := root का बाएं
    • अन्यथा जब चाल "R" के समान है, तो root := root का दाएं
    • अन्यथा,
      • past से अंतिम तत्व हटाएं
      • root := past से अंतिम तत्व और इसे past से हटाएं
  • root का मान लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण


class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, moves):
        past = []
        for move in moves:
            past.append(root)
            if move == "L":
                root = root.left
            elif move == "R":
                root = root.right
            else:
                past.pop()
                root = past.pop()
        return root.val

ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R", "R", "U", "L"]
print(ob.solve(root, traverse))

इनपुट

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
["R","R","U","L"]

आउटपुट

3
  1. पायथन में बाइनरी ट्री के किसी भी पथ का सबसे बड़ा योग खोजने का प्रोग्राम पायथन में बाइनरी ट्री के किसी भी पथ का सबसे बड़ा योग खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट नोड से लीफ नोड तक जाने वाले किसी भी पथ का सबसे बड़ा योग ढूंढना है। उदाहरण के लिए, यदि इनपुट जैसा है: तो आउटपुट 29 होगा क्योंकि रूट से, यदि हम पथ 5-<9-<7-<8 का पालन करते हैं तो जोड़ के बाद यह 29 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

  1. पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम पायथन में बाइनरी ट्री की अधिकतम चौड़ाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें ट्री में किसी भी स्तर की अधिकतम चौड़ाई ढूंढनी है। यहां एक स्तर की चौड़ाई उन नोड्स की संख्या है जो बाएं सबसे नोड और दाएं सबसे नोड के बीच रखे जा सकते हैं। उदाहरण के लिए, यदि इनपुट है: तो आउटपुट होगा 2। हल करने के चरण एक मैप d बनाएं, न्यूनतम और अधिकतम मान

  1. पायथन में बाइनरी ट्री उल्टा करें पायथन में बाइनरी ट्री उल्टा करें

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमारा कार्य एक उल्टा बाइनरी ट्री बनाना है। यदि ट्री नीचे जैसा है: उल्टा ट्री इस तरह होगा: इसे हल करने के लिए हम एक पुनरावर्ती दृष्टिकोण का उपयोग करेंगे: यदि रूट null है, तो वापस करें बाएं और दाएं पॉइंटर्स को स्वैप करें बाएं सबट्री और दाएं सबट्री के लिए पुनर