[LeetCode] 110. Balanced Binary Tree

110. Balanced Binary Tree

LeetCode

 

Given a binary tree, determine if it is height-balanced.

이진 트리(Binary Tree)가 주어졌을 때, 해당 트리가 높이 균형(Height-balanced)이 잡힌 상태인지 판별하세요.

 

Example

Input: root = [3,9,20,null,null,15,7]
Output: true

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Input: root = []
Output: true

---

1. 문제 요구사항 분석

균형이진트리인지 묻는 문제: 노드의 높이가 2이상 차이나면 균형이진트리 조건 불충분

2. 접근 전략

DFS로 구현하기

import java.util.*;

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 도우미 함수가 가져온 최종 보고서가 '-1'이 아니면 참!
        return checkHeight(root) != -1;
    }

    public int checkHeight(TreeNode root) { // 매개변수로 height를 받지 않습니다!
        
        if (root == null) return 0;
       
        int leftHeight = checkHeight(root.left);
        int rightHeight = checkHeight(root.right);
        
        // 하위 중 -1 발견 시 -1 return
        if (leftHeight == -1 || rightHeight == -1) return -1;
        
        // 균형 깨진 상황 (차이 2 이상)
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        
        // 정상
        return Math.max(leftHeight, rightHeight) + 1;
    }
}