108. Convert Sorted Array To Binary Search Tree

108. Convert Sorted Array To Binary Search Tree (Easy) 降有序数组转换为二叉搜索树

题干

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

解法

朴素解法

有序数组，组成高度平衡的二叉搜索树。重点就在于找到中间值，然后左右区间分别构造二叉树的左右子树。

递归解法

• 输入参数：输入一个数组
• 输出参数：输出一个二叉树节点
• 终止条件：
  • 当数组长度等于1时，返回二叉树节点，值等于元素，左右子节点等于None
• 单层核心逻辑：
  • 当前数组长度整除2，结果就是中间值的index
  • 将当前中间值作为value
  • 分别把左区间[0:index]和右区间[index+1:]的返回值，当作当前节点的左右子节点

# 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]:
        len_nums = len(nums)
        if len_nums < 1:
            return None
        elif len_nums == 1:
            return TreeNode(nums[0])
        root_i = len_nums // 2
        root = TreeNode(nums[root_i])
        root.left = self.sortedArrayToBST(nums[:root_i])
        root.right = self.sortedArrayToBST(nums[root_i+1:])
        return root