110. Balanced Binary Tree ☆

110. Balanced Binary Tree

✅ 정답 접근 방식

• 모든 서브트리에서 좌우 높이 차가 1 이하여야 함
• 재귀적으로 하향하면서, 각 노드의 서브트리 균형 여부까지 함께 체크해야 함
• 보통은 dfs() 함수에서 높이(height)를 리턴하면서, 불균형이면 특수값(-1 등)을 리턴하는 방식이 깔끔해요

---

최종 코드

🔧 정답 코드 (DFS 방식, 높이와 균형 여부 동시에 판단)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 높이가 balanced 이면 return True, 좌우 높이차이가 1까지..는 balance

        def dfs(node):
            if not node: # 노드가 none 이면 
                return 0
            if not node.left and not node.right: # 리프노드, 자식없는 마지막노드이면
                return 1

            # 자식 노드 개수 계산
            left = dfs(node.left)            
            right = dfs(node.right)
            if left == -1 or right == -1: # 둘중 하나라도 불균형 발생하면 특수값 -1 반환
                return -1
            
            diff = abs(left-right)
            if diff >= 2: # 현재 불균형 발생하면 특수값 -1 반환
                return -1

            return 1+ max(left, right)

        if not root:
            return True

        
        return dfs(root) != -1

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # 일반 바이너리 트리에 발란스 잇는지 보려면, 모든 노드 돌면서, 높이가 1이상 차이가 나는지 확인
        def dfs(node):
            # 높이 리턴하는걸로
            # 발란스 깨지면 -1리턴
            if not node:
                return 0
            if not node.left and not node.right: # 리프노드면
                return 1

            l = dfs(node.left)
            r = dfs(node.right)
            if l == -1 or r == -1: # 자식이 하나라도 비정상이면
                return -1

            # 현재 노드 기준 비정상이면
            if abs(l-r) > 1:
                return -1
            
            # 현재 노드 높이 반환
            return 1+max(l, r)

        height = dfs(root)
        return True if height != -1 else False