[1스4코2파] # 164. LeetCode 124. Binary Tree Maximum Path Sum

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (164차)
[4코1파] 2023.01.13~ (156일차)
[1스4코1파] 2023.04.12~ (67일차)
[1스4코2파] 2023.05.03 ~ (46일차)

Today :

2023.06.15 [164일차]
LeetCode

124. Binary Tree Maximum Path Sum

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

문제 설명

주어진 이진 트리에서, 어떤 노드에서 시작해서 어떤 노드에서 끝나는 경로 중에서 경로 합의 최대 값을 반환한다.
경로는 이진 트리의 루트 노드에서 시작하여 어떤 노드에서 끝나는 노드들의 시퀀스를 나타내고, 이 경로는 임의의 노드에서 시작하고 임의의 노드에서 끝날 수 있다.

문제 풀이 방법

이진 트리의 각 노드를 방문하면서, 해당 노드를 경로의 일부로 포함하거나 제외하는 경우의 수를 계산해야 한다. dfs로 노드를 타고 내려가면서 재귀적으로 노드를 탐색하고, 현재 노드를 포함한 경우와 포함하지 않은 경우를 따로 고려하면서 최대 경로 합을 계산한다.

내 코드

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:
        ans = [root.val]
        def dfs(node):
            if not node:
                return 0

            leftMax, rightMax = dfs(node.left), dfs(node.right)

            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            ans[0] = max(ans[0], node.val+leftMax + rightMax)
            return node.val + max(leftMax, rightMax)

        dfs(root)
        return ans[0]      

증빙

여담

그나마 하드치고는 괜찮은 문제 였다