मान लीजिए हमारे पास एक गैर-खाली बाइनरी ट्री है। हमें पथ योग ढूंढना है। तो यहां, एक पथ कुछ प्रारंभिक नोड से किसी भी नोड तक नोड्स का कोई अनुक्रम है जहां पैरेंट-चाइल्ड कनेक्शन मौजूद हैं। पथ में कम से कम एक नोड होना चाहिए और रूट नोड से गुजरने की आवश्यकता नहीं है। इसलिए यदि इनपुट ट्री है −
यहां आउटपुट 32 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
solve() नामक एक विधि परिभाषित करें, यह नोड लेगा
यदि नोड null है या नोड का मान 0 है, तो 0 लौटाएं
left := 0 और solve(नोड के बाएं) का अधिकतम
right := 0 और solve(नोड के दाएं) का अधिकतम
ans := ans और left + right + नोड के डेटा का अधिकतम
नोड डेटा + left और right का अधिकतम लौटाएं
मुख्य विधि से, ans := -inf सेट करें, फिर solve(root) कॉल करें और ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def maxPathSum(self, root): self.ans = -float('inf') self.solve(root) return self.ans def solve(self,node): if not node or node.data == 0: return 0 left = max(0,self.solve(node.left)) right = max(0,self.solve(node.right)) self.ans = max(self.ans,left+right+node.data) return node.data + max(left,right) ob = Solution() root = make_tree([-10,9,10,None,None,15,7]) print(ob.maxPathSum(root))इनपुट
[-10,9,10,None,None,15,7]
आउटपुट
32
