1. 문제 출처

LeetCode 1373번 문제

2. 문제 설명

이진 트리의 루트 노드가 주어졌을 때, 부분 트리 중에서 이진 검색 트리(BST)를 이루는 것들의 최대 노드 합계를 반환하세요. BST 조건은 다음과 같습니다:

• 왼쪽 서브트리의 모든 노드 값이 현재 노드 값보다 작음
• 오른쪽 서브트리의 모든 노드 값이 현재 노드 값보다 큼
• 왼쪽/오른쪽 서브트리 모두 BST를 만족함

3. 예시

입력: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
출력: 20  // 값이 3인 서브트리가 최대 합 BST

입력: root = [4,3,null,1,2]
출력: 2  // 값이 2인 단일 노드가 최대 합 BST

입력: root = [-4,-2,-5]
출력: 0  // 모든 노드가 음수이므로 빈 트리

4. 해결 전략

후위 순회 방식으로 각 노드를 검사하며 BST 여부를 판단합니다. 각 서브트리에서 다음 정보를 수집합니다:

1. 서브트리 내 최소값
2. 서브트리 내 최대값
3. 서브트리 노드 합계

현재 노드의 값이 왼쪽 서브트리의 최대값보다 크고, 오른쪽 서브트리의 최소값보다 작아야 BST 조건을 만족합니다. BST인 경우 전역 최대값을 갱신합니다.

5. 코드 구현

class Solution {
    private int maxSum;  // 최대 BST 합계 저장
    
    static class TreeStats {
        int minVal;
        int maxVal;
        int totalSum;
        
        TreeStats(int min, int max, int sum) {
            minVal = min;
            maxVal = max;
            totalSum = sum;
        }
    }
    
    public int maxSumBST(TreeNode root) {
        maxSum = 0;
        traverse(root);
        return maxSum;
    }
    
    private TreeStats traverse(TreeNode node) {
        if (node == null) {
            return new TreeStats(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }
        
        TreeStats leftStats = traverse(node.left);
        TreeStats rightStats = traverse(node.right);
        
        if (node.val <= leftStats.maxVal || node.val >= rightStats.minVal) {
            return new TreeStats(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
        }
        
        int currentSum = leftStats.totalSum + rightStats.totalSum + node.val;
        maxSum = Math.max(maxSum, currentSum);
        
        return new TreeStats(
            Math.min(leftStats.minVal, node.val),
            Math.max(rightStats.maxVal, node.val),
            currentSum
        );
    }
}

6. 복잡도 분석

• 시간 복잡도: O(n) - 모든 노드를 정확히 한 번 방문
• 공간 복잡도: O(h) - 재귀 호출 스택 깊이(h는 트리 높이), 최악의 경우 O(n)