​LeetCode刷题实战108:将有序数组转换为二叉搜索树

共 1573字,需浏览 4分钟

 ·

2020-11-30 22:37

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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.

题意


将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

样例

解题


二叉搜索树是一种树种每个节点都大于它的左子节点,小于它的右子节点的树。如果中序遍历二叉搜索树,则结果为一个有序序列。

由二叉搜索树的性质可知,题目中给定有序数组的中间数即为根节点,中间数左边的序列为根节点的左子树,右边的序列为根节点的右子树,依次类推,因此,可以采用二分法来解题。


# 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:
        return self.BST(nums, 0, len(nums)-1)
    def BST(self, nums, start, end):
        if start > end:
            return None
        mid = (start + end)//2
        cur = TreeNode(nums[mid])
        cur.left = self.BST(nums, start, mid-1)
        cur.right = self.BST(nums, mid + 1, end)
        return cur


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:
LeetCode1-100题汇总,希望对你有点帮助!
LeetCode刷题实战101:对称二叉树
LeetCode刷题实战102:二叉树的层序遍历
LeetCode刷题实战103:二叉树的锯齿形层次遍历
LeetCode刷题实战104:二叉树的最大深度
LeetCode刷题实战105:从前序与中序遍历序列构造二叉树
LeetCode刷题实战106:从中序与后序遍历序列构造二叉树
LeetCode刷题实战107:二叉树的层次遍历 II

浏览 27
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报