108. 将有序数组转换为二叉搜索树

Posted on Edited on In Views: Word count in article: 821 Reading time ≈ 1 mins.

108. 将有序数组转换为二叉搜索树

题目链接：108. 将有序数组转换为二叉搜索树

题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

核心思考：中分数组与分治策略构建体系

如果随意抓取数字强行做二叉探索树堆搭，极其容易让其因为向心偏单产生滑铁卢塌缩导致严重左倾右翻（演变退化成为线性长链条）。为了保证构筑的二叉搜索树是高度完美平衡无暇的，这需要两头重量分布极度均等！

得益于输入数组原本已经是严格升序排布好的属性，最佳也是最理所当然的做法即是：直接选取正中央的轴座坐标 m = len(nums) // 2 将这尊人物选定为树这片领地的最高王冠（父/根）。
接着，采用经典的分治 (Divide and Conquer) 大手一挥斩波分断：

  1. 中位定位建根：拿出这个中间地带 nums[m] 初始化出一个 TreeNode 头目节点。
  2. 割裂派发授权：
    • 将这截面左方这批清一色比中间小弱的成员 nums[:m] 发配给左子庭进行全套相同制度打磨，构建属于他们专属的左次级平衡子构架树。
    • 同理这下盘截断靠后体量普遍丰厚强壮的成员体 nums[m+1:] 全部发送给到右方统筹建立他们的右从属平衡系统架构树区。
  3. 如果下行下潜传达到最后面临无源空地切段为空，返回个 None 完结断交就行了。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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
        left = self.sortedArrayToBST(nums[:m])
        right = self.sortedArrayToBST(nums[m + 1:])
        
        return TreeNode(nums[m], left, right)

复杂度分析

  • 时间复杂度：O(N)，这里 N 为数组拥护群数字长总长。我们所构建的全版大盘大旗里总共有 N 个人物树形化诞生了对应 N 次；唯一的掣肘在于用切片方法虽然易读极精干快捷但每次创建全新分支副本在后台会有额外产生微小的数组切割搬运流逝，如对效率绝对狂热追求极致的话可采用设立传入两端游标下标锁定而非物理切片切割会更精湛到最真神还原。
  • 空间复杂度：O(log N) 的潜入潜寻回调追踪堆栈留痕；只要这是棵足够精明对等稳赢的健康双分分拆平衡木架这树深就稳扎在极限的对数深级。