LeetCode #1339 Maximum Product of Splitted Binary Tree

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1339 Maximum Product of Splitted Binary Tree

문제 풀이

dfs를 한 번 수행하여 전체 합을 수하게 만들고 중간 리턴 시 자기 포함 하단 노드들의 합을 반환하여 이후 2번째 dfs에서 앞서 구한 전체합과 비교하게 한다.

• 클래스 변수와 전체 합을 0으로 선언
• dfs 함수를 정의한다. 좌, 우측의 sub_tree합을 구하고 양쪽의 결과 비교하여 최대값을 클래스 변수에 저장한다.
• 리턴은 자신 포함 양쪽 sub_tree 합을 더한 값을 리턴하여 전체 합이 마지막으로 반환되게 설정
• 첫 dfs는 전체 합을 구하게끔 탐색
• 두 번째 dfs에서 전체 합이 설정되어 클래스 변수 값이 설정됨
• 제약 조건에 따라 나머지 연산 후 반환

python 코드

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        MOD = 10 ** 9 + 7
        self.res = total = 0
        def dfs(node):
            if node is None:
                return 0
            left, right = dfs(node.left), dfs(node.right)
            self.res = max(self.res, left * (total - left), right * (total - right))
            return left + right + node.val
        total = dfs(root)
        dfs(root)
        return self.res % MOD