[LeetCode 110] Balanced Binary Tree (Java)

🚀 문제 분석

• 목표: 주어진 이진 트리가 높이 균형(Height-Balanced)이 잡혀 있는지 판별합니다.
• 조건: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하여야 합니다.
• 핵심: 각 노드의 높이를 계산함과 동시에, 어느 한 곳이라도 균형이 깨졌다면 즉시 그 정보를 상단으로 전달해야 합니다.

💡 해결 전략: 상향식(Bottom-up) 높이 계산 및 상태 전파

가장 효율적인 방법은 트리의 리프(Leaf)부터 높이를 재면서 올라오는 것입니다.

1. 높이 측정: 각 노드는 max(왼쪽 높이, 오른쪽 높이) + 1을 통해 자신의 높이를 부모에게 보고합니다.
2. 균형 체크: 높이를 계산할 때 |왼쪽 높이 - 오른쪽 높이| > 1인지 확인합니다.
3. 상태 전파 (-1의 의미):
   • 만약 균형이 깨졌다면, 높이 대신 -1을 리턴합니다.
   • 자식 노드 중 하나라도 -1을 리턴했다면, 현재 노드도 계산을 중단하고 즉시 -1을 반환하여 루트까지 불균형 상태를 전파합니다. (조기 종료)

💻 구현 코드 (Java)

public class Solution_Leetcode_110 {

    public boolean isBalanced(TreeNode root) {
        // 결과가 -1이 아니라면 균형 잡힌 트리
        return dfs(root) != -1;
    }

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

        // 1. 왼쪽 서브트리 체크
        int left = dfs(node.left);
        // 2. 오른쪽 서브트리 체크
        int right = dfs(node.right);

        // 3. 조기 종료 및 균형 판별
        // 자식 중 하나라도 불균형(-1)이거나, 현재 위치에서 높이 차가 1 초과인 경우
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }

        // 4. 정상이라면 현재 노드의 높이 반환
        return Math.max(left, right) + 1;
    }
}

🧐 기술적 고찰

• 효율성: 한 번의 순회($O(N)$)로 높이 계산과 균형 판별을 동시에 수행합니다. 불균형 발견 시 불필요한 연산을 건너뛰는 -1 전파 방식이 핵심입니다.
• 공간 복잡도: 재귀 호출 스택을 고려할 때 트리의 높이 $H$만큼의 공간인 $O(H)$를 사용합니다.
• 재귀의 묘미: 단순히 값을 구하는 재귀에서 한 걸음 나아가, 특정 조건 충족 여부를 특수한 리턴값(-1)으로 설계하여 에러 처리(Error Handling)와 유사한 흐름을 만든 점이 훌륭한 포인트입니다.