1. 문제 소개

1339. Maximum Product of Splitted Binary Tree

2. 나의 풀이

힌트를 보며 풀었는데, dfs를 통해 이진트리의 합을 구하고, 부분합과 총합의 차를 계산하며 푸는 방식이다.
모든 노드를 한 번씩 방문해 시간복잡도는 $O(n)$이다.

class Solution:                                              # LeetCode 제출 형식에 맞춘 Solution 클래스 정의
    def maxProduct(self, root: Optional[TreeNode]) -> int:    # 간선 하나를 끊어 얻는 곱의 최댓값을 반환하는 함수
        MOD = 10**9 + 7                                       # 문제에서 요구하는 모듈러 상수 설정

        def tree_sum(node):                                   # 트리 전체 합을 구하는 DFS 함수 정의
            if not node:                                      # 현재 노드가 None이면 합은 0
                return 0                                      # 빈 서브트리의 합 반환
            return node.val + tree_sum(node.left) + tree_sum(node.right)  # 현재 노드 + 좌/우 서브트리 합 반환
        
        total = tree_sum(root)                                # 트리의 전체 노드 합을 미리 계산
        ans = 0                                               # 최대 곱을 저장할 변수 초기화

        def subtree_sum(node):                                # 각 노드의 서브트리 합을 계산하며 최대 곱을 갱신하는 DFS 함수
            nonlocal ans                                      # 바깥 스코프의 ans를 갱신하기 위해 nonlocal 선언

            if not node:                                      # 현재 노드가 None이면 서브트리 합은 0
                return 0                                      # 빈 서브트리의 합 반환

            left_sum = subtree_sum(node.left)                 # 왼쪽 서브트리 합을 재귀적으로 계산
            right_sum = subtree_sum(node.right)               # 오른쪽 서브트리 합을 재귀적으로 계산

            sub = node.val + left_sum + right_sum             # 현재 노드를 루트로 하는 서브트리의 총합 계산

            ans = max(ans, sub * (total - sub))               # 이 서브트리로 분리했을 때의 곱으로 최대값 갱신
            
            return sub                                        # 현재 서브트리 합을 상위 호출로 반환

        subtree_sum(root)                                     # 루트부터 서브트리 합 계산 DFS를 실행하여 ans를 채움

        return ans % MOD                                      # 최대 곱을 MOD로 나눈 값을 반환

3. 다른 풀이

하나의 dfs 함수로만 푼 방식도 존재한다.

class Solution:                                                  # LeetCode 제출용 Solution 클래스 정의
    def maxProduct(self, root: Optional[TreeNode]) -> int:       # 간선 하나를 끊어 얻을 수 있는 최대 곱을 구하는 함수
        ans, total = -inf, 0                                     # ans는 최대 곱, total은 트리 전체 합을 저장할 변수

        def dfs(root):                                          # DFS로 서브트리 합을 계산하는 내부 함수 정의
            nonlocal ans, total                                  # 외부 스코프의 ans, total 변수를 사용하기 위해 선언
            if not root:                                        # 현재 노드가 None인 경우
                return 0                                        # 서브트리 합은 0으로 반환
            Sum = root.val + dfs(root.left) + dfs(root.right)   # 현재 노드를 루트로 하는 서브트리 합 계산
            ans = max(ans, (total - Sum) * Sum)                 # 현재 서브트리를 기준으로 분리했을 때의 곱으로 최대값 갱신
            return Sum                                          # 계산된 서브트리 합을 상위 호출로 반환

        total = dfs(root)                                       # 첫 DFS로 트리 전체 합(total)을 계산
        dfs(root)                                               # 두 번째 DFS로 모든 서브트리 분할 경우를 검사
        return ans % (10**9 + 7)                                 # 최대 곱을 모듈러 연산 후 반환

4. 마무리

이번에는 좀 어려웠으나 이해하고보니 쉬운 문제였다.