पायथन में एक पेड़ के गैर-आसन्न नोड्स की अधिकतम राशि खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें उन मानों का अधिकतम योग ज्ञात करना होगा जो प्राप्त किए जा सकते हैं, कोई भी दो मान बच्चे के आसन्न माता-पिता नहीं हो सकते हैं।

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

तो आउटपुट 17 होगा क्योंकि 10, 4, 3 एक दूसरे से सटे नहीं हैं।

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

फ़ंक्शन f() को परिभाषित करें। यह नोड लेगा
यदि नोड शून्य है, तो
- वापसी (0, 0)
(a, b) :=f(नोड के बाएं)
(c, d) :=f(नोड के दाएं)
एक जोड़ी लौटाएं (नोड + बी + डी और ए + सी, ए + सी का अधिकतम मूल्य)
मुख्य विधि से f(root) को कॉल करें और इसका पहला मान लौटाएं

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

उदाहरण

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.val = data
   self.left = left
   self.right = right
def f(node):
   if not node:
      return 0, 0
   a, b = f(node.left)
   c, d = f(node.right)
   return max(node.val + b + d, a + c), a + c
class Solution:
   def solve(self, root):
      return f(root)[0]
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(3) print(ob.solve(root))

इनपुट

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(10)
root.left.left = TreeNode(4)
root.left.right = TreeNode(3)