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

पायथन में दिए गए ट्री से सबसे बड़ा बाइनरी सर्च सबट्री खोजने का प्रोग्राम


मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें सबसे बड़ा सबट्री (अधिकतम नोड्स के साथ) ढूंढना है जो बाइनरी सर्च ट्री हो।

उदाहरण के लिए, यदि इनपुट ट्री है:

पायथन में दिए गए ट्री से सबसे बड़ा बाइनरी सर्च सबट्री खोजने का प्रोग्राम

तो आउटपुट होगा:

पायथन में दिए गए ट्री से सबसे बड़ा बाइनरी सर्च सबट्री खोजने का प्रोग्राम

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम पोस्ट-ऑर्डर ट्रैवर्सल का उपयोग करेंगे:

  • max_size := [0], max_node := [null]
  • traverse(node) फंक्शन परिभाषित करें:
    • यदि node null है, तो खाली लिस्ट लौटाएं
    • left := traverse(node.left)
    • right := traverse(node.right)
    • lst := left + [node.val] + right
    • यदि lst सॉर्टेड है:
      • यदि max_size[0] < len(lst) है, तो max_size[0] := len(lst) और max_node[0] := node
    • lst लौटाएं
  • traverse(root) कॉल करें
  • max_node[0] लौटाएं

पायथन कार्यान्वयन

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

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.val, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, root):
        max_size = [0]
        max_node = [None]
        def traverse(node):
            if not node:
                return []
            left = traverse(node.left)
            right = traverse(node.right)
            lst = left + [node.val] + right
            if sorted(lst) == lst:
                if max_size[0] < len(lst):
                    max_size[0] = len(lst)
                    max_node[0] = node
            return lst
        traverse(root)
        return max_node[0]

ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))

इनपुट

root = TreeNode(12) root.left = TreeNode(3) root.right = TreeNode(5) root.right.left = TreeNode(4) root.right.right = TreeNode(6)

आउटपुट

4, 5, 6,
  1. पायथन में दिए गए बाइनरी ट्री में सबसे बड़ा पूर्ण उपट्री खोजें पायथन में दिए गए बाइनरी ट्री में सबसे बड़ा पूर्ण उपट्री खोजें

    मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इस बाइनरी ट्री में अधिकतम पूर्ण उप-ट्री का आकार ढूंढना है। जैसा कि हम जानते हैं, एक पूर्ण बाइनरी ट्री वह बाइनरी ट्री है जहां सभी स्तर पूरी तरह भरे होते हैं, संभवतः अंतिम स्तर को छोड़कर, और अंतिम स्तर में सभी कुंजियां यथासंभव बाईं ओर होती हैं। इसलिए, यदि इ

  1. Python में दिए गए बाइनरी ट्री के वर्टिकल लेवल को क्रमबद्ध है या नहीं जांचना Python में दिए गए बाइनरी ट्री के वर्टिकल लेवल को क्रमबद्ध है या नहीं जांचना

    मान लीजिए हमारे पास बाइनरी ट्री है; हमें जांचना है कि बाइनरी ट्री का दिया गया वर्टिकल लेवल क्रमबद्ध है या नहीं। जब दो नोड ओवरलैप हो रहे हों, तो जांचें कि वे उस लेवल से संबंधित हैं जहां वे क्रमबद्ध क्रम में हैं। तो, यदि इनपुट l = -1 है तो आउटपुट True होगा, क्योंकि लेवल -1 में तत्व 3, 7 हैं और वे क्र

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

    मान लीजिए हमारे पास एक दिया गया बाइनरी ट्री है; हमें उस दिए गए बाइनरी ट्री में सबसे बड़े परफेक्ट सब-ट्री का आकार ढूंढना है। जैसा कि हम जानते हैं, परफेक्ट बाइनरी ट्री एक बाइनरी ट्री है जिसमें सभी आंतरिक नोड्स के दो बच्चे होते हैं और सभी पत्ते समान स्तर पर होते हैं।तो, यदि इनपुट इस तरह है:तो आउटपुट 3