পাইথনে সর্বোচ্চ গড় সাবট্রি ভ্যালু

মনে করুন আমাদের একটি বাইনারি ট্রির রুট দেওয়া আছে, আমাদের সেই ট্রির যেকোনো সাবট্রির সর্বোচ্চ গড় ভ্যালু বের করতে হবে।

ট্রি যদি নিচের মতো হয়:

আউটপুট হবে 6, কারণ নোড ৫ এর জন্য গড় (5+6+1)/3 = 4, নোড ৬ এর জন্য 6/1 = 6, নোড ১ এর জন্য 1/1 = 1, তাই সর্বোচ্চ 6।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (পোস্ট-অর্ডার ট্রভার্সাল):

• res := 0

• solve(root) মেথড ডিফাইন করুন:

  • যদি root না থাকে, তবে [0, 0] রিটার্ন করুন।

  • left := solve(root.left), right := solve(root.right)

  • c := left[0] + right[0] + 1 (নোড কাউন্ট)

  • s := left[1] + right[1] + root.val (সামগ্রিক সম)

  • ans := max(ans, s/c)

  • return [c, s]

• মেইন মেথডে ans := 0, solve(root) কল করুন, ans রিটার্ন করুন।

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

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