a-059-binary-tree-maximum-path-sum2026-07-05hardleetcode #124neetcode150

이진 트리 최대 경로 합

#dynamic-programming#tree#depth-first-search#binary-tree

↗ leetcode #124 · a-059-binary-tree-maximum-path-sum

문제

· problem

P.a-059-binary-tree-maximum-path-sum

이진 트리 최대 경로 합

이진 트리의 경로는 인접한 노드 쌍이 간선으로 연결된 노드의 수열입니다. 각 노드는 수열에 최대 한 번만 나타날 수 있습니다. 경로가 반드시 루트를 지나야 하는 것은 아닙니다. 경로의 경로 합은 경로에 포함된 노드 값들의 합입니다. 이진 트리의 루트가 주어질 때, 임의의 0이 아닌 경로의 최대 경로 합을 반환하세요.

제약

· The number of nodes in the tree is in the range [1, 3 * 10^4]
· -1000 ≤ Node.val ≤ 1000

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[1,2,3]

example 2input → output

[-10,9,20,null,null,15,7]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
경로가 루트를 반드시 포함해야 하나요?
☐
경로가 한 노드에서 양쪽 자식으로 동시에 갈 수 있나요?
☐
음수 노드 값이 있을 때 그것을 건너뛸 수 있나요?
☐
단일 노드만 있는 경로도 유효한가요?
☐
DFS 함수는 왜 '분기 경로'의 합을 반환하지 않고 '선형 경로'의 합을 반환하나요?
☐
왜 음수 부경로를 0으로 '리셋'합니까?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 초기값 설정

○

res = [root.val]

○

res = float('-inf')

○

res = [0]

step 2· DFS 함수 정의

○

def dfs(root):

○

def dfs(root, res):

○

def dfs(root):
    global res

step 3· 좌우 서브트리에서 최대 확장 경로 계산│ 중첩

○

leftMax = dfs(root.left)

○

leftMax = max(dfs(root.left), 0)
rightMax = max(dfs(root.right), 0)

○

leftMax = dfs(root.left) + dfs(root.right)

step 4· 음수 기여도를 0으로 리셋│ 중첩

○

leftMax = max(leftMax, 0)

○

leftMax = max(leftMax, -1000)

○

if leftMax < 0:
    leftMax = 0

step 5· 이 노드에서 분기하는 경로로 전역 최대값 업데이트│ 중첩

○

res[0] = max(res[0], root.val + leftMax + rightMax)

○

res[0] = max(res[0], leftMax + rightMax)

○

res[0] = root.val + leftMax + rightMax - 1

step 6· 부모로 확장 가능한 경로 반환│ 중첩

○

return root.val + max(leftMax, rightMax)

○

return root.val + leftMax + rightMax

○

return max(leftMax, rightMax)

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

# 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: TreeNode) -> int:

        res = [root.val]

        # return max path sum without split

        def dfs(root):

            if not root:

                return 0

            leftMax = dfs(root.left)

            rightMax = dfs(root.right)

            leftMax = max(leftMax, 0)

            rightMax = max(rightMax, 0)

            # compute max path sum WITH split

            res[0] = max(res[0], root.val + leftMax + rightMax)

            return root.val + max(leftMax, rightMax)

        dfs(root)

        return res[0]

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[1,2,3]

→

case 2

[-10,9,20,null,null,15,7]

→

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.