[LEET CODE] 110. Balanced Binary Tree

# Problem

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as:     Constraints: The number of nodes in the tree is in the range [0, 5000]. -104 <= Node.val <= 104

 

# My Answer

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if root is None:
            return True
       
        # 트리 높이 계산    
        def height(rt):
            if not rt:
                return -1
            return 1 + max(height(rt.left),height(rt.right))
            
        a = True
        b = True
         
        # 서브 트리도 균형인지 확인
        if root.left:
            a = self.isBalanced(root.left)
        if root.right:
            b = self.isBalanced(root.right)
            
        if abs(height(root.left)-height(root.right)) > 1:
            return False
            
        return a and b # 서브 트리도 모두 균형인지 확인

 

# Solution 1 - 재귀 구조로 높이 차이 계산

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check(root):
            if not root:
                return 0

            left = check(root.left)
            right = check(root.right)
            
            # 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
                
            return max(left, right) + 1

        return check(root) != -1

서브 트리 중 하나가 -1이 되면 부모노드 까지 계속 -1 을 리턴하게 됨

처음에 리프 노드는 1의 값을 가짐 ( 리프 노드의 자식 (None) 이 0의 값을 가짐 )