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

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

इसलिए, यदि इनपुट इस तरह है

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

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

एक फ़ंक्शन f() परिभाषित करें। यह node लेगा
यदि node null है, तो
- (0, 0) वापस करें
(a, b) := f(node का बायाँ)
(c, d) := f(node का दायाँ)
एक जोड़ी वापस करें (node के मान + b + d और a + c का अधिकतम, a + c)
मुख्य विधि से 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)