nums라는 숫자 목록이 있다고 가정합니다. 이 목록은 트리의 inorder traversal에서 리프 노드를 나타냅니다. 여기서 내부 노드는 2개의 자식을 가지며 그 값은 왼쪽 서브트리의 가장 큰 잎값과 오른쪽 서브트리의 가장 큰 잎값의 곱과 같습니다. 값의 최소 합으로 트리의 합을 찾아야 합니다.
따라서 입력이 nums =[3, 5, 10]과 같으면 출력은 83이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- res :=num에 있는 모든 요소의 합
- 숫자 크기> 1, do
- i :=숫자의 최소 요소 인덱스
- left :=nums[i - 1] 일 때 i> 0 그렇지 않으면 무한대
- right :=nums[i + 1] if i
- res :=res + (왼쪽과 오른쪽의 최소값) * nums의 i번째 요소, nums에서 i번째 요소 삭제
- 반환 결과
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시 코드
class Solution:
def solve(self, nums):
res = sum(nums)
while len(nums) > 1:
i = nums.index(min(nums))
left = nums[i - 1] if i > 0 else float("inf")
right = nums[i + 1] if i < len(nums) - 1 else float("inf")
res += min(left, right) * nums.pop(i)
return res
ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums)) 입력
[3, 5, 10]
출력
83