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

तो आउटपुट 62 होगा क्योंकि नोड्स [12, 13, 14, 16, 7] हैं।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
utils()फ़ंक्शन परिभाषित करें जोrootलेता है।यदि
rootnull है, तो 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लौटाएं।मुख्य विधि से:
यदि
rootnull है, तो 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