題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請(qǐng)你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。
高度平衡二叉樹是一棵滿足「每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1 」的二叉樹。

示例

輸入：nums = [-10,-3,0,5,9]
輸出：[0,-3,9,-10,null,5]
解釋：[0,-10,5,null,-3,null,9] 也將被視為正確答案：
輸入：nums = [1,3]
輸出：[3,1]
解釋：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索樹。

思路

選擇中間數(shù)字作為二叉搜索樹的根節(jié)點(diǎn)，這樣分給左右子樹的數(shù)字個(gè)數(shù)相同或只相差 11，可以使得樹保持平衡。如果數(shù)組長(zhǎng)度是奇數(shù)，則根節(jié)點(diǎn)的選擇是唯一的，如果數(shù)組長(zhǎng)度是偶數(shù)，則可以選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)或者選擇中間位置右邊的數(shù)字作為根節(jié)點(diǎn)，選擇不同的數(shù)字作為根節(jié)點(diǎn)則創(chuàng)建的平衡二叉搜索樹也是不同的。
確定平衡二叉搜索樹的根節(jié)點(diǎn)之后，其余的數(shù)字分別位于平衡二叉搜索樹的左子樹和右子樹中，左子樹和右子樹分別也是平衡二叉搜索樹，因此可以通過遞歸的方式創(chuàng)建平衡二叉搜索樹。

Python

# 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]:
        def helper(left, right):
            if left > right:
                return None

            # 總是選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)
            mid = (left + right) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(nums) - 1)