Convert Sorted Array to Binary Search Tree

문제 링크 : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Convert Sorted Array to Binary Search Tree - LeetCode

문제 해설 : 모든 요소(elements)가 오름차순으로 정렬된 정수 배열 nums가 주어집니다. 이 배열을 높이가 균형 잡힌 이진 탐색 트리로 변환하세요.

높이가 균형 잡힌 이진 탐색 트리란, 모든 노드에 대해 좌우의 서브 트리의 깊이의 차가 1 이하인 이진 탐색 트리를 말합니다.

 

제한 사항

1) nums의 길이는 [1, 10^4]를 만족합니다.

2) nums[i]의 크기는 [-10^4, 10^4]를 만족합니다.

3) nums는 강한 오름차순으로 정렬되어있습니다.

 

 

사용된 용어부터 난해한 문제였습니다.

이진 탐색 트리를 구현하되 모든 노드에 대해 서브 트리의 높이가 2 이상 차이나지 않도록 하는 것이 문제의 요지입니다.

이 때, 제한사항으로 주어진 강한 오름차순은 임의의 정수 x, y에 대해 x < y라면 nums[x] < nums[y]가 항상 참이라는 뜻입니다. (즉, 서로 같은 요소가 없음을 의미합니다.)

 

 

from typing import List

# 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 generateTree(self, nums: List[int], L: int, R: int) -> TreeNode:
        if L > R:
            return None
            
        mid = (L + R) // 2
        node = TreeNode(nums[mid])
        node.left = self.generateTree(nums, L, mid-1)
        node.right = self.generateTree(nums, mid+1, R)
        return node
        
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        return self.generateTree(nums, 0, len(nums)-1)

nums가 이미 오름차순으로 정렬되어 있으므로

재귀적으로 nums안의 요소를 탐색하며 새로운 node를 생성하고

nums의 탐색 범위를 좌,우로 좁혀 서브 트리를 생성해 연결하는 방식으로 구현했습니다.

 

가능한 정답이 여럿 있지만 문제에서 제시한 사항을 위배하지 않으면 모두 정답처리 되므로

가장 직관적으로 해결할 수 있는 재귀함수를 사용했습니다.