[LeetCode 1038] BST to Greater Sum Tree (Java)

🚀 문제 분석

• 목표: 이진 탐색 트리(BST)를 Greater Sum Tree(GST)로 변환합니다.
• 조건: GST의 각 노드는 기존 노드 값 + 기존 BST에서 해당 노드보다 큰 모든 노드 값의 합을 가집니다.
• 핵심: BST에서 나보다 큰 값들은 항상 내 오른쪽 서브트리에 존재한다는 점을 활용해야 합니다.

💡 해결 전략: 역순 중위 순회 (Reverse In-order Traversal)

가장 큰 값부터 거꾸로 방문하며 누적 합(Prefix Sum)을 구하는 방식입니다.

1. 우측 우선 탐색: 가장 큰 값들이 몰려 있는 root.right부터 재귀적으로 방문합니다.
2. 누적 합 업데이트: 전역 변수 sum에 현재 노드의 값을 더하고, 현재 노드의 값을 이 sum으로 업데이트합니다.
3. 좌측 탐색: 이제 나보다 작은 값들이 있는 root.left로 이동하여 앞서 구한 sum을 계속 전달하며 업데이트합니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_1038 {

    // 현재까지 방문한 노드들의 누적 합을 저장
    private int sum = 0;

    public TreeNode bstToGst(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 1. 오른쪽 서브트리 방문 (가장 큰 값부터 시작)
        bstToGst(root.right);

        // 2. 현재 노드 처리 및 누적 합 업데이트
        sum += root.val;
        root.val = sum;

        // 3. 왼쪽 서브트리 방문 (나보다 작은 값들 처리)
        bstToGst(root.left);

        return root;
    }
}

🧐 기술적 고찰

• BST의 속성 활용: 중위 순회(In-order)가 오름차순을 보장한다면, 그 반대인 Right -> Root -> Left 순회는 내림차순을 보장합니다. 이를 통해 $O(N \log N)$의 정렬 과정 없이 $O(N)$만으로 모든 노드를 적절한 순서로 방문했습니다.
• 변수 생명주기: sum을 멤버 변수로 선언하여 재귀 호출 간에 상태를 공유하도록 설계했습니다. 이는 별도의 파라미터 전달 없이도 누적 상태를 유지하는 간결한 방식입니다.
• 공간 복잡도: 추가적인 트리 생성 없이 기존 트리의 값을 변경(In-place)하므로 메모리 효율적이며, 재귀 스택 깊이만큼인 $O(H)$ (트리의 높이) 공간을 사용합니다.