LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree

简介: LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree

LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告


一、中文版

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

     0

    / \

  -3   9

  /   /

-10  5

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


二、英文版

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

     0

    / \

  -3   9

  /   /

-10  5

 

三、My answer

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        def helper(nums, start, end):
            if start > end:
                return None
            node = TreeNode(nums[ceil((start + end)/2)])
            node.left = helper(nums,start, ceil((start+end)/2)-1)
            node.right = helper(nums, ceil((start+end)/2)+1, end)
            return node
        return helper(nums,0, len(nums)-1)


四、解题报告

数据结构:树、数组

实现:递归

算法:每次选取数据的中间值作为根节点,中间值左右两边继续寻找中间值作为左右子树的根节点。

注意:本人尝试了 int() 和 // 发现都是向下取整,本题中要使用 ceil() 才对。

关于 Python 取整方法及比较,详见:

https://blog.csdn.net/u011675334/article/details/106023033

相关文章
|
30天前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
9 1
|
30天前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
15 1
|
30天前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
34 0
|
30天前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
8 0
|
30天前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
11 0
|
30天前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
8 0
|
30天前
【LeetCode 41】530.二叉搜索树的最小绝对差
【LeetCode 41】530.二叉搜索树的最小绝对差
9 0
|
30天前
【LeetCode 40】98.验证二叉搜索树
【LeetCode 40】98.验证二叉搜索树
11 0
|
30天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0
|
3月前
|
算法
LeetCode第96题不同的二叉搜索树
文章介绍了LeetCode第96题"不同的二叉搜索树"的解法,利用动态规划的思想和递推公式,通过计算以任意节点为根的不同二叉搜索树的数量,解决了该问题。
LeetCode第96题不同的二叉搜索树