给你一个整数数组 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% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/373