LeetCode/Convert Sorted Array to Binary Search Tree

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 이 m / p 로 b ぇ ms / ]

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1
2개의 subtree 사이의 깊이에 2이상의 차이가 없는 tree'를 만들 수 있다고 합니다.

해답·해설

해법 1

2개의 subtree 사이의 깊이도 1보다 큰 차이가 없는 것 같은 트리는 여러가지 생각되는 것입니다만, 문제문에도 있던 아래 그림과 같이,

(binarytree 라이브러리로 만들어 보았습니다만 이마이치군요...)

대원의 루트에서 좌우에 2개의 subtree가 나오고, 나머지는 1개밖에 subtree가 없는 듯한 트리를 생각해, 2개의 subtree의 깊이에 2 이상의 차이가 없는 트리
을 만드는 것이 간단한 알고리즘입니다. 보다 구체적으로는
[-10, -3, 0, 5, 9] -> left: [-10, -3], root: 0, right: [5, 9]
와 같이, 중앙값을 root로 하고, 중앙값보다 전의 값의 리스트를 root.left로, 중앙값보다 후의 값의 리스트를 root.right로 합니다.
그런 다음 root.left와 root.right에 대해 동일한 작업을 수행하는 재귀 구조로 만듭니다.

# Definition for a binary tree node.
# 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
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

해법 2

Discussion을 바라보고 있으면, 리스트의 슬라이스는 비용이 높다는 것으로, 수정안이 있었습니다.

class Solution: 
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def convert(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            node = TreeNode(nums[mid])
            node.left = convert(left, mid - 1)
            node.right = convert(mid + 1, right)
            return node
        return convert(0, len(nums) - 1)

파이썬 작업에 대한 비용은 다음 페이지에 정리되어 있습니다.

[ htps : // 우우키. py 응. 오 rg / moin / chimeko mp ぃ ty : 에 m 베 d : ]