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

1. 문제 설명

문제 링크: LeetCode 124 - Binary Tree Maximum Path Sum

요약: 이진 트리의 노드들을 연결하는 경로 중 노드 값들의 합이 최대가 되는 경로를 찾는 문제입니다. 경로는 반드시 루트를 지날 필요가 없으며, 어느 노드에서 시작하여 어느 노드에서 끝나도 상관없지만 경로 내 노드는 중복될 수 없습니다.

2. 핵심 아이디어

이 문제는 트리의 각 노드를 '경로의 정점(Peak)'으로 가정하고 재귀(DFS)를 통해 상향식(Bottom-up)으로 해결합니다.

• 독립적인 경로 vs 연장 가능한 경로:
  • 어떤 노드에서 부모 노드로 전달할 값은 '해당 노드와 왼쪽 자식 중 큰 값' 또는 '해당 노드와 오른쪽 자식 중 큰 값'이어야 합니다. (한 갈래로만 연결 가능)
  • 반면, 현재 노드를 정점으로 삼는 최대 경로는 '왼쪽 자식 + 현재 노드 + 오른쪽 자식'의 합으로 계산됩니다.
• 음수 값 처리: 만약 자식 노드로부터 올라온 경로의 합이 음수라면, 차라리 해당 경로를 포함하지 않는 것이 이득입니다. 따라서 Math.max(sum, 0) 처리를 통해 음수 합을 차단합니다.
• 전역 변수 활용: 재귀적으로 모든 노드를 방문하면서, 각 노드를 정점으로 하는 최대 경로 합을 전역 변수 max에 계속 갱신합니다.

3. 코드

Java

 

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        calcSum(root);
        return max;
    }

    private int calcSum(TreeNode node) {
        if (node == null) return 0;

        int leftSum = calcSum(node.left);
        int rightSum = calcSum(node.right);

        int currMax = Math.max(leftSum, rightSum) + node.val;
        max = Math.max(max, leftSum + node.val + rightSum);

        return Math.max(currMax, 0);
    }
}

4. 코드 포인트 해설

• Math.max(calcSum, 0): 트리의 노드 값에 음수가 포함될 수 있기 때문에 매우 중요한 로직입니다. 자식 노드의 경로 합이 -5라면 이를 더하는 것보다 무시하는 것이 전체 합을 키우는 방법입니다.
• 역할의 분리: calcSum 함수는 두 가지 일을 동시에 수행합니다.
  1. 전역 변수 max에는 현재 노드를 중심으로 하는 완성된 형태의 경로 합을 갱신합니다.
  2. 함수 반환값으로는 부모 노드와 연결될 수 있는 최대 한 갈래의 합을 전달합니다.
• 초기값 Integer.MIN_VALUE: 모든 노드의 값이 음수일 수 있으므로 max를 0이 아닌 가장 작은 정수 값으로 설정해야 정확한 비교가 가능합니다.

5. 성능 및 복잡도

• 시간 복잡도: 모든 노드를 한 번씩 방문하므로 $O(N)$입니다.
• 공간 복잡도: 트리의 높이를 $H$라고 할 때, 재귀 호출 스택의 깊이에 따라 $O(H)$를 사용합니다. 최악의 경우(편향 트리) $O(N)$이 될 수 있습니다.

6. 마치며

이진 트리에서의 최대 경로는 "현재 노드를 경로에 포함할 것인가?"와 "포함한다면 부모로 무엇을 넘겨줄 것인가?"를 결정하는 것이 핵심입니다.

이번 문제는 하드로 분류되어 있지만 문제 수준은 이지로 봐도 무방할듯 합니다.

궁금한 점이 있다면 언제든 알려주세요!