Giả sử chúng ta có gốc của cây nhị phân; chúng ta phải tìm giá trị trung bình lớn nhất của bất kỳ cây con nào của cây đó. Vì vậy, nếu cây như -
Đầu ra sẽ là 6, điều này là do, đối với nút 5, nó sẽ là (5 + 6 + 1) / 3 =4, sau đó đối với nút 6, nó sẽ là 6/1 =6 và đối với nút 1, nó sẽ là 1/1 =1, vì vậy giá trị lớn nhất là 6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=0
-
Xác định một phương thức có tên là giải quyết (), phương thức này sẽ có giá trị root
-
nếu gốc chưa được đặt, thì trả về một cặp [0, 0]
-
left:=giải quyết (bên trái của thư mục gốc) phải:=giải quyết (bên phải thư mục gốc)
-
c:=left [0] + right [0] + 1
-
s:=left [1] + right [1] + giá trị của root
-
ans:=max of and ans s / c
-
trả về một cặp [c, s]
-
Từ phương thức chính, đặt ans:=0, gọi giải quyết (root) và trả về ans
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[5,6,1]
Đầu ra
6.0