题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小的二叉搜索树。

示例:

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

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

          0
         / \
       -3   9
       /   /
     -10  5

题目思考

  1. 如何构造可以使得高度最小?

解决方案

思路

  • 要使得高度最小, 一个最直观的思路就是将数组中点作为树的根, 然后左右区间也利用同样的思路, 依次递归分治构建树
  • 这样能够保证左右子树的节点数目差最小, 从而高度差也最小, 对应的也就是最小高度树了

复杂度

  • 时间复杂度 O(N): 每个节点只需要遍历一遍
  • 空间复杂度 O(logN): 递归栈需要保存二叉树高度个节点, 而其高度显然是 logN

代码

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        # 递归分治创建二叉搜索树
        def build(s, e):
            if s > e:
                return None
            # 先找到当前区间中点, 并构造根
            m = (s + e) >> 1
            root = TreeNode(nums[m])
            # 然后根节点的左右子节点分别是左右区间的根节点
            root.left = build(s, m - 1)
            root.right = build(m + 1, e)
            return root

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

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我