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

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


मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें रूट नोड से लीफ नोड तक जाने वाले किसी भी पथ का सबसे बड़ा योग ढूंढना है।

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

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

  • walk() फंक्शन परिभाषित करें जो node, s लेता है:
    • यदि node null है, तो max_sum := max(max_sum, s), वापस करें
    • s := s + node का डेटा
    • walk(node का बायां, s)
    • walk(node का दायां, s)
  • मुख्य विधि से:
    • max_sum := 0
    • walk(root, 0)
    • max_sum वापस करें

उदाहरण

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

class Solution:
    def walk(self, node, s):
        if not node:
            self.max_sum = max(self.max_sum, s)
            return
        s += node.data
        self.walk(node.left, s)
        self.walk(node.right, s)
    def solve(self, root):
        self.max_sum = 0
        self.walk(root, 0)
        return self.max_sum

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

इनपुट

root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)

आउटपुट

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

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

  1. Python में बाइनरी ट्री अधिकतम पथ योग Python में बाइनरी ट्री अधिकतम पथ योग

    मान लीजिए हमारे पास एक गैर-खाली बाइनरी ट्री है। हमें पथ योग ढूंढना है। तो यहां, एक पथ कुछ प्रारंभिक नोड से किसी भी नोड तक नोड्स का कोई अनुक्रम है जहां पैरेंट-चाइल्ड कनेक्शन मौजूद हैं। पथ में कम से कम एक नोड होना चाहिए और रूट नोड से गुजरने की आवश्यकता नहीं है। इसलिए यदि इनपुट ट्री है −यहां आउटपुट 32

  1. पायथन में पथ योग पायथन में पथ योग

    मान लीजिए हमारे पास एक ट्री और एक योग है। हमें एक ऐसा पथ ढूंढना है जिससे यदि हम उस पथ का अनुसरण करें, तो हमें वह योग मिलेगा जो दिए गए योग से मेल खाता हो। मान लीजिए ट्री [0,-3,9,-10, null,5] जैसा है और योग 14 है, तो एक पथ 0 → 9 → 5 है। हल करने के चरण यदि रूट null है, तो False वापस करें यदि बायां औ