पायथन में अधिकतम औसत सबट्री

मान लीजिए हमारे पास एक बाइनरी ट्री का रूट है; हमें उस ट्री के किसी भी सबट्री का अधिकतम औसत मान ढूंढना है। इसलिए यदि ट्री इस तरह है -

आउटपुट 6 होगा, ऐसा इसलिए क्योंकि, नोड 5 के लिए, यह (5 + 6 + 1)/ 3 = 4 होगा, फिर नोड 6 के लिए यह 6 / 1 = 6 होगा, और नोड 1 के लिए, यह 1 / 1 = 1 होगा, इसलिए अधिकतम 6 है।

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

• res := 0

• solve() नामक एक मेथड परिभाषित करें, यह root लेगा

• यदि root सेट नहीं है, तो [0, 0] जोड़ी लौटाएं

• left := solve(root का बायां) right := solve(root का दायां)

• c := left[0] + right[0] + 1

• s := left[1] + right[1] + root का मान

• ans := ans और s/c का अधिकतम

• [c, s] जोड़ी लौटाएं

• मुख्य मेथड से, ans := 0 सेट करें, 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 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