[LeetCode] 110. Balanced Binary Tree

😎풀이

해당 문제에서 언급된 height-balanced된 tree는 높이의 차이가 2이상 나지 않는 것을 의미한다.

즉 1 까지의 차이는 검증하지 않음

자식 노드에서 문제된 -1은 부모 노드로 전이되며 추가 탐색하지 않게끔 구현하면 시간복잡도 줄이기에 용이하다.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isBalanced(root: TreeNode | null): boolean {
    // 높이를 계산하는 헬퍼 함수
    // 트리가 균형잡히지 않았을 경우 -1을 반환
    function getHeight(node: TreeNode | null): number {
        // 기저 케이스: 빈 노드는 높이가 0
        if (node === null) return 0;
        
        // 왼쪽 서브트리의 높이를 구함
        const leftHeight = getHeight(node.left);
        // 이미 불균형이 발견되었다면 더 이상 진행하지 않음
        if (leftHeight === -1) return -1;
        
        // 오른쪽 서브트리의 높이를 구함
        const rightHeight = getHeight(node.right);
        // 이미 불균형이 발견되었다면 더 이상 진행하지 않음
        if (rightHeight === -1) return -1;
        
        // 왼쪽과 오른쪽 서브트리의 높이 차이가 1보다 크면 불균형
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        
        // 현재 노드의 높이를 반환 (더 큰 서브트리의 높이 + 1)
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    // getHeight 함수가 -1을 반환하지 않으면 트리가 균형잡혀있다는 의미
    return getHeight(root) !== -1;
}