Heero

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        
        mid = len(nums) // 2
        
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        
        return root

배열이 먼저 정렬되어 있어야 한다.

이진 검색을 하는 것과 유사하게 구현한다. 숫자 리스트 중 중앙값보다 작은 값이 왼쪽, 중앙값보다 큰 값이 오른쪽으로 오게 하고, nums의 범위를 변경함으로써 재귀 탐색을 한다.

// 내림 연산자를 사용하여 중앙값을 탐색할 수 있게 한다.

# 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:
        
        def check(node):
            if not node:
                return 0
            
            left = check(node.left)
            right = check(node.right)
            
            if left == -1 \
                or right == -1 \
                or abs(left-right) > 1:
                return -1
            
            return max(left, right) + 1
    
        return check(root) != -1

체크포인트

• leaf 노드 탐색을 if not node (None인지 체크)로 수행
• leaf 노드 도달 시 탐색를 종료하는 동시에 상태값을 0으로 저장
• 현 노드 상태값은 max(left, right) + 1로 저장