[파이썬] 배열을 바이너리 서치 트리로 변환 ( array to height balanced Binary Search Tree)

주어진 (정렬된) 배열에 대해서 높인 균형 이진탐색 트리로 변환하는 코드입니다.

재귀적으로 방법으로 간단히 해결할 수 있습니다.

 

Array to Balanced BST

 

class TreeNode():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        
def array_to_bst(nums):
    if not nums:
        return None  
    
    # 중앙 인덱스
    mid_idx = len(nums)//2
    
    # 중앙값으로 노드 생성
    node = TreeNode(nums[mid_idx])
    
    # left subtree 구성
    # values < nums[mid_idx]
    node.left = array_to_bst(nums[:mid_idx])
    
    # right subtree 구성
    # values > nums[mid_idx]
    node.right = array_to_bst(nums[mid_idx+1:])
    
    return node

def inorder(node): 
    if not node: 
        return      
    
    inorder(node.left) 
    print(node.val)
    inorder(node.right)   

    
nums = [1,2,3,4,5,6,7]
print("Original array:", nums)

root = array_to_bst(nums)
print("A height balanced BST:")
print(inorder(root))

 

함께 보면 좋은 글:

https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-binary-search-tree-exercise-5.php

https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-binary-search-tree-exercise-5.php