바이너리 트리의 루트가 있다고 가정합니다. 우리는 해당 트리의 모든 하위 트리의 최대 평균값을 찾아야 합니다. 트리가 다음과 같다면 -
출력은 6이 되는데, 이는 노드 5의 경우 (5 + 6 + 1)/3 =4이고 노드 6의 경우 6/1 =6이고 노드 1의 경우 다음과 같기 때문입니다. 1 / 1 =1이므로 최대값은 6입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
해상도 :=0
-
solve()라는 메서드를 정의하면 루트가 됩니다.
-
루트가 설정되지 않은 경우 [0, 0] 쌍을 반환합니다.
-
왼쪽 :=해결(루트의 왼쪽) 오른쪽 :=해결(루트의 오른쪽)
-
c :=왼쪽[0] + 오른쪽[0] + 1
-
s :=왼쪽[1] + 오른쪽[1] + 루트 값
-
ans :=최대 및 ans s/c
-
쌍을 반환[c, s]
-
기본 메소드에서 as :=0으로 설정하고 solve(root)를 호출하고 as를 리턴합니다.
예시(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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