मान लीजिए कि हमारे पास एक बाइनरी ट्री की जड़ है; हमें उस पेड़ के किसी भी उप-वृक्ष का अधिकतम औसत मान ज्ञात करना है। तो अगर पेड़ जैसा है -
आउटपुट 6 होगा, ऐसा इसलिए है, क्योंकि नोड 5 के लिए, यह (5 + 6 + 1)/3 =4 होगा, फिर नोड 6 के लिए यह 6/1 =6 होगा, और नोड 1 के लिए यह होगा 1/1 =1, इसलिए अधिकतम 6 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रेस :=0
-
हल () नामक विधि को परिभाषित करें, यह जड़ लेगा
-
यदि रूट सेट नहीं है, तो एक जोड़ी लौटाएं [0, 0]
-
बाएँ:=हल करें (मूल के बाएँ) दाएँ:=हल करें (मूल का दाएँ)
-
सी :=बाएँ[0] + दाएँ[0] + 1
-
s :=बाएँ[1] + दाएँ[1] + मूल का मान
-
उत्तर :=अधिकतम और उत्तर s/c
-
एक जोड़ी लौटाएं[सी, एस]
-
मुख्य विधि से, उत्तर सेट करें:=0, हल (रूट) को कॉल करें और उत्तर वापस करें
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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 helper(self, node): if not node: return 0, 0 left_sum, left_count = self.helper(node.left) right_sum, right_count = self.helper(node.right) self.ans = max(self.ans, (left_sum + right_sum + node.data) / (left_count + right_count + 1)) return left_sum + right_sum + node.data, left_count + right_count + 1 def maximumAverageSubtree(self, root): self.ans = 0 self.helper(root) return self.ans ob = Solution() root = make_tree([5,6,1]) print(ob.maximumAverageSubtree(root))
इनपुट
[5,6,1]
आउटपुट
6.0