leetcode - Tree - Binary Tree Level Order Traversal II

 

이번 문제는 정렬된 List<int>를 인자로 받아 높이가 균등한 balanced binary search tree를 만드는 문제입니다.

 

트리의 사용 이유중에는 정렬을 위해서도 있지만, 문제에서는 이미 정렬된 문자열을 주기 때문에

문자열의 중간값을 찾고 중간에서부터 각 왼쪽과 오른쪽값들은 현재 노드에서 왼쪽과 오른쪽으로 넘겨주면 자연스럽게

높이가 균등한 BST가 완성되게 됩니다.

 

코드는 아래와 같습니다.

 

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums: return None

        mid = len(nums) // 2

        res = TreeNode(nums[mid])
        res.left = self.sortedArrayToBST(nums[:mid])
        res.right = self.sortedArrayToBST(nums[mid+1:])
        return res

 

감사합니다.