124. Binary Tree Maximum Path Sum

[zeikar]

Problem link

https://leetcode.com/problems/binary-tree-maximum-path-sum/

Problem Summary

이진 트리가 있을 때 트리 상의 경로 중에 합이 가장 큰 경로를 구하는 문제.

Solution

어려워 보이지만 subproblem으로 나누면 의외로 간단하다

일단 현재 노드에서의 최대 합을 구한다면 왼쪽 -> 현재 노드 -> 오른쪽 서브트리의 최대가 최대 합이 될 것이다.
그런데 구현할 때 위의 값 그대로 리턴하면 안되는데 경로가 중복될 수 있기 때문이다. 따라서 함수에서 리턴은 왼쪽 서브트리를 거쳐 루트로 올라갈 때의 최대 합, 오른쪽 서브트리를 거쳐 루트로 올라갈 때의 최대 합 중에 최대로 리턴해줘야 한다.
함수 중간에서 최대 합을 계속 갱신해주면서 계산하면 된다. 그냥 아래 코드 참고.

서브트리의 값을 구할 때 0이랑 max를 해준 이유는 그냥 해당 서브트리를 선택을 안한 경우이다. 합이 음수이면 경로에 포함하지 않는 것이 좋다.

Source Code

import math
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        maxim = -math.inf

        def max_sum(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            left_sum = max(0, max_sum(node.left))
            right_sum = max(0, max_sum(node.right))

            nonlocal maxim
            maxim = max(maxim, node.val + left_sum + right_sum)

            return max(node.val + left_sum, node.val + right_sum)

        max_sum(root)
        return maxim