Leetcode 1339: 갈라진 두 갈래 나무의 최대 곱셈(초상세 해법!!!)

너에게 두 갈래 나무 한 그루를 줄게, 그것의 뿌리는 root 이다.두 갈래 나무를 두 그루의 나무로 분열시키고 그 나무와 곱셈은 가능한 한 크게 하세요.
답이 매우 클 수 있기 때문에, 결과를 10^9+7로 추출한 후에 다시 되돌려 주십시오.
예 1:

 ：root = [1,2,3,4,5,6]
 ：110
 ： ，  2  ，  11   10 。  110 （11*10）

예 2:

 ：root = [1,null,2,3,4,null,null,5,6]
 ：90
 ： ，  2  ，  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] 사이입니다.

문제 풀이 사고방식
수형 문제는 우선 사고의 귀착해이다.각 노드에 대해 말하자면, 우리는 각각 왼쪽 연결을 삭제하고 오른쪽 연결을 삭제하는 해를 고려한 다음에 최대 값을 취하면 된다.
귀속을 통해 우리는 왼쪽 연결을 삭제한 후 왼쪽 트리의 합l까지 할 수 있다.오른쪽 연결을 삭제한 후 오른쪽 하위 트리의 합r을 삭제합니다.그러면 왼쪽 연결을 삭제한 후의 해답은 l*(total - l)이다.오른쪽 연결을 삭제한 후의 해답은 r*(total - r)total는 나무 전체의 합을 표시하고 두 갈래 나무를 훑어보며 구한다.

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        total = 0
        def inOrder(node):
            nonlocal total
            if node:
                inOrder(node.left)
                total += node.val
                inOrder(node.right)
        inOrder(root)
        
        mod, res = 10**9 + 7, 0
        def dfs(node):
            nonlocal res
            if not node:
                return 0
            
            l, r = dfs(node.left), dfs(node.right)
            res =  max(res, l * (total - l), r * (total - r))
            return l + r + node.val
        
        dfs(root)
        return res % mod

실제로 코드는 더욱 간결할 수 있다.우리의 dfs 함수 반환값은 root 을 뿌리로 하는 나무의 합이다. 그러면 우리는 두 번 dfs 함수를 호출하면 된다.

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        total, mod, res = 0, 10**9 + 7, 0
        def dfs(node):
            nonlocal res
            if not node:
                return 0
            
            l, r = dfs(node.left), dfs(node.right)
            res =  max(res, l * (total - l), r * (total - r))
            return l + r + node.val
        
        total = dfs(root)
        dfs(root)
        return res % mod

reference:
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/discuss/496549/JavaC%2B%2BPython-Easy-and-Concise
이 질문의 다른 언어 버전을 GitHub Leetcode에 추가했습니다.
문제가 있으면 여러분이 지적해 주시기 바랍니다!!!

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Leetcode 104: 두 갈래 나무의 최대 깊이(가장 자세한 해법!!!)

두 갈래 나무를 정해 최대 깊이를 찾아라. 두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 포크 트리 지정[3,9...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Leetcode 1339: 갈라진 두 갈래 나무의 최대 곱셈(초상세 해법!!!)

좋은 웹페이지 즐겨찾기