LeetCode刷题 NO.108 将有序数组转为二叉搜索树 (简单)

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例

解析

1）二叉树相关的问题，优先考虑递归；

2）要求树是高度平衡的，所以用二分法即可。

代码示例

# 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]:
        return self.recursion(nums)

    def recursion(self, lst):
        if len(lst) == 0:
            return None
        mid = (0 + len(lst)) // 2
        node = TreeNode(lst[mid])
        node.left = self.recursion(lst[0:mid])
        node.right = self.recursion(lst[mid+1:len(lst)])
        return node

执行用时：36 ms, 在所有 Python3 提交中击败了 97.77% 的用户.