[LeetCode] 124. Binary Tree Maximum Path Sum 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Binary Tree Maximum Path Sum

---

문제 요약

이진 트리가 주어질 때, 어떤 경로(Path)의 합이 최대가 되는 값을 구하라.

경로는 부모-자식으로 연결
시작과 끝은 아무 노드 가능
반드시 루트를 지날 필요는 없음

• 문제 링크: https://leetcode.com/problems/binary-tree-maximum-path-sum

---

💡 사고의 출발점: 경로는 어떻게 생겼을까?

문제를 다시 읽어보자.

“어떤 경로든 상관없다.”

👉 트리에서 경로는 어떤 모양일까?

• 트리는 사이클이 없다.
• 그래서 모든 경로는 반드시 이런 형태다.

왼쪽 어딘가
    ↑
   (정점)
    ↓
오른쪽 어딘가

즉, 모든 경로는 반드시 하나의 “정점(peak)”을 가진다.

---

💡 첫 번째 핵심: 현재 노드를 정점으로 가정해보자

만약 현재 노드가 경로의 가장 위(peak)라면?
그 경로는 이렇게 된다.

• left + node + right

왼쪽에서 가장 좋은 경로
현재 노드
오른쪽에서 가장 좋은 경로


이게 바로 global max 후보가 된다.

---

💡 두 번째 핵심: 부모에게는 무엇을 주어야 할까?

이제 재귀 관점으로 생각해보자.

parent
           |
         node
        /    \
      left   right

• 부모는 경로를 “이어가야” 한다.
• 그런데 만약 node가 left + node + right를 부모에게 넘기면 어떻게 될까?

그럼 경로는 이렇게 된다.

• left → node → right → parent

여기서 문제가 발생한다.

• node에서 경로가 두 갈래로 갈라진다.
• 경로는 직선이어야 한다.
• Y자 모양이면 안 된다.

그래서 부모에게는 반드시 node + max(left, right) 한 방향만 전달해야 한다.

---

💡 세 번째 핵심: 왜 0을 고려할까?

다음 질문

만약 left 값이 음수라면?

경로는 선택 사항이다.
그 가지를 “아예 안 쓰는 선택”도 가능하다.

그래서 자연스럽게

• left = Math.max(0, dfs(root.left));

음수 가지는 버린다.
이것은 최대값 문제에서의 합리적인 선택이다.

---

🧠 사고 흐름 정리

각 노드에서 우리는 동시에 두 가지를 계산한다.

1️⃣ 이 노드가 경로의 정점이라면?

left + node + right → global max 갱신


2️⃣ 이 노드가 부모로 이어지는 통로라면?

node + max(left, right) → 재귀 반환값

---

✅ 최종 코드 (Java)

class Solution {

    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;

        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));

        // 현재 노드를 경로의 정점으로 사용
        maxSum = Math.max(maxSum, left + right + root.val);

        // 부모에게 전달할 값 (한 방향만)
        return root.val + Math.max(left, right);
    }
}

📈 시간 / 공간 복잡도

• 시간: O(N)→ 모든 노드를 한 번씩 방문
• 공간: O(H) → 재귀 스택 깊이 (트리 높이)

---

📝 이번 문제에서 얻은 진짜 교훈

• 트리 문제는 “경로의 구조”를 먼저 생각하자
• 트리 문제는 항상 서브 트리로 쪼개서 생각하자
• 모든 경로는 반드시 하나의 정점을 가진다
• 최대 문제에서는 음수를 버릴 수 있다는 것을 기억하자