LeetCode-Python-1343. 분열 트리의 최대 곱셈(DFS)
1932 단어 Leetcode
답이 매우 클 수 있기 때문에, 결과를 10^9+7로 추출한 후에 다시 되돌려 주십시오.
예 1:
입력: 루트=[1,2,3,4,5,6] 출력: 110 해석: 빨간색 테두리를 삭제하고 나무 두 그루를 얻을 수 있으며 각각 11과 10입니다.그것들의 곱셈은 110(11*10) 예 2:
입력: 루트=[1,null,2,3,4,null,null,5,6] 출력: 90 해석: 빨간색 테두리를 제거하고 나무 두 그루를 얻을 수 있습니다. 각각 15와 6입니다.90(15*6)의 곱셈 예제 3:
입력: root = [2,3,9,10,7,8,6,5,4,11,1] 출력: 1025 예 4:
입력: root = [1,1] 출력: 1
팁:
나무마다 최대 50000개의 노드가 있고 적어도 2개의 노드가 있다.각 노드의 값은 [1, 10000] 사이입니다.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/maximum-product-of-splitted-binary-tree저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.
생각:
먼저 각 노드를 뿌리로 하는 자수의 합을 계산해서 해시표에 저장하고 키는 각 노드,val은 자수의 합이다.
그리고 임의의 노드 Node에 대해 부모 노드와 절단한 후 두 나무의 곱셈은 다음과 같습니다.
(원래 트리 총 - 노드를 루트로 하는 하위 트리의 합)* 노드를 루트로 하는 하위 트리의 합
최대치를 찾으면 됩니다.
시간 복잡도: O(N)
공간 복잡도: O(N)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxProduct(self, root):
"""
:type root: TreeNode
:rtype: int
"""
dic = {}
def SumOfTree(node):
if not node:
return 0
ls, rs = SumOfTree(node.left), SumOfTree(node.right)
dic[node] = ls + rs + node.val
return dic[node]
SumOfTree(root)
TotalSum = dic[root]
self.res = 0
def dfs(node):
if not node:
return
tmp = (TotalSum - dic[node]) * dic[node]
self.res = max(self.res, tmp)
dfs(node.left)
dfs(node.right)
dfs(root)
return self.res % (10 ** 9 + 7)이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
