資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚
法律Python中最大平均子樹\n
假設我們有二叉樹的根，我們必須找到該樹任何子樹的最大平均值。所以如果樹如下 -
輸出將是 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(根的左子樹) right := solve(根的右子樹)
c := left[0] + right[0] + 1
s := left[1] + right[1] + 根的值
ans := 與 ans s/c 的最大值
返回一對 [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
更新於：2020 年 4 月 30 日
138 次瀏覽
廣告