当前位置：首页 > article >正文

【leetcode100】将有序数组转换为二叉搜索树

article 2025/1/22 18:31:17

1、题目描述

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵

平衡二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

2、初始思路

2.1 思路

平衡二叉树 是指该树所有节点的左右子树的高度相差不超过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]:
        if not nums:
            return None
        m = len(nums) // 2
        return TreeNode(nums[m],self.sortedArrayToBST(nums[:m]),self.sortedArrayToBST(nums[m+1:]))

查看全文

http://www.kler.cn/a/513838.html