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

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


मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें किन्हीं दो नोड्स के बीच किसी भी पथ का अधिकतम योग ढूंढना है।

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

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

तो आउटपुट 62 होगा क्योंकि नोड्स [12, 13, 14, 16, 7] हैं।

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

  • utils() फ़ंक्शन परिभाषित करें जो root लेता है।

  • यदि root null है, तो 0 लौटाएं।

  • l := utils(root.left), r := utils(root.right)।

  • max_single := max(max(l, r) + root.val, root.val)।

  • max_top := max(max_single, l + r + root.val)।

  • res := max(res, max_top) (ग्लोबल अधिकतम अपडेट करें)।

  • max_single लौटाएं।

  • मुख्य विधि से:

    • यदि root null है, तो 0 लौटाएं।

    • res := -infinity।

    • utils(root) कॉल करें।

    • res लौटाएं।

उदाहरण

class TreeNode:    def __init__(self, value):       self.val = value       self.left = None       self.right = None class Solution:    def solve(self, root):       if root is None:          return 0       self.res = float("-inf")       self.utils(root)       return self.res    def utils(self, root):       if root is None:          return 0       l = self.utils(root.left)       r = self.utils(root.right)       max_single = max(max(l, r) + root.val, root.val)       max_top = max(max_single, l + r + root.val)       self.res = max(self.res, max_top)       return max_single ob = Solution() root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7) print(ob.solve(root))

इनपुट

root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)

आउटपुट

62

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

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

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

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

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

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