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

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

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

तो, अगर इनपुट पसंद है

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

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

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

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

  • अगर रूट अशक्त है, तो

    • वापसी 0

  • l :=utils (रूट के बाएँ)

  • r :=utils(रूट के दायें)

  • max_single:=अधिकतम (अधिकतम l और r) + रूट का मान) और रूट का मान

  • max_top :=max_single का अधिकतम और l + r + रूट का मान

  • रेस :=अधिकतम रेस और मैक्स_टॉप

  • वापसी max_single

  • मुख्य विधि से, निम्न कार्य करें -

  • अगर रूट शून्य है, तो

    • वापसी 0

  • रेस:=इन्फिनिटी

  • बर्तन (रूट)

  • रिटर्न रेस

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

उदाहरण

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 . होगा इसे हल करने के लिए, हम इन चरणों का पालन करेंगे- न्य

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

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