LeetCode | 面试题 04.02. 最小高度树【Python】

曾经终败给现在 2022-11-08 14:08 145阅读 0赞

## 问题 ##

[力扣][Link 1]

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

**示例:**

给定有序数组: [-10,-3,0,5,9],
    
    一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
    
          0 
         / \ 
       -3   9 
       /   / 
     -10  5

## 思路 ##

**递归**

二叉搜索树根节点一定是有序数组的中位数：长度为奇数则取唯一中位数，长度为偶数则取右中位数。
    递归终止条件：有序数组为空

## 代码 ##

### Python3 ###

# 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
            
            mid = len(nums) // 2
            root = TreeNode(nums[mid])
            root.left = self.sortedArrayToBST(nums[:mid])
            root.right = self.sortedArrayToBST(nums[mid + 1:])
    
            return root

## 链接 ##

[GitHub][]

[Link 1]: https://leetcode-cn.com/problems/minimum-height-tree-lcci/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/tree/master/solutions/Interview-04.02-Minimum-Height-Tree-LCCI

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关拓扑排序变种题：Leetcode310最小高度树

拓扑排序变种题：Leetcode310最小高度树问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

末蓝、/ 2023年10月06日 09:22/ 0 赞/ 14 阅读

相关程序员面试金典-面试题04.02-最小高度树

程序员面试金典-面试题04.02-最小高度树上周实现了一个二叉查找树（BST），感觉对于二叉树的操作更加熟练了，然后就找“程序员面试金典”相对应的二叉树的题目，做了四道

╰+攻爆jí腚メ/ 2023年01月10日 11:59/ 0 赞/ 156 阅读

相关 Leetcode310. 最小高度树--基于拓扑排序求解此问题

Leetcode310. 最小高度树–基于拓扑排序求解此问题思想:由边界向中心逐渐收缩，直至收缩到最里层。 class Solution {

淡淡的烟草味﹌/ 2023年01月09日 03:57/ 0 赞/ 133 阅读

相关最小高度树

> leetcode 310 题 \[medium\] > 中: [最小高度树][Link 1] > 英: [Minimum Height Trees][] > !

朱雀/ 2022年12月23日 13:28/ 0 赞/ 145 阅读

相关面试题 04.02. 最小高度树

题目来源 [https://leetcode-cn.com/problems/minimum-height-tree-lcci/][https_leetcode-cn.c

一时失言乱红尘/ 2022年12月18日 01:58/ 0 赞/ 127 阅读

相关 leetcode 310. 最小高度树拓扑排序

使用邻接矩阵会超时使用邻接表就不超时了每次去掉度为1的点到最后的两个以内的时候停止 define debug(x) cout<<x<<": "<<(

偏执的太偏执、/ 2022年12月16日 05:54/ 0 赞/ 137 阅读

相关 LeetCode面试题 04.02. 最小高度树 JAVA

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例: 给定有序数组: [-10,-3,0,5,9],

痛定思痛。/ 2022年12月13日 04:54/ 0 赞/ 136 阅读

相关 LeetCode 面试题 04.02. 最小高度树

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。思路是由于要创建高度最小的二叉树，并且输入数组是有序的，因此可以先找出中间元素，

小灰灰/ 2022年12月05日 10:22/ 0 赞/ 163 阅读

相关 310. 最小高度树（JS实现）

1 题目 > 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函

忘是亡心i/ 2022年11月27日 15:59/ 0 赞/ 152 阅读

相关 LeetCode | 面试题 04.02. 最小高度树【Python】

问题 [力扣][Link 1] 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例: 给定有序数组: [-1

曾经终败给现在/ 2022年11月08日 14:08/ 0 赞/ 146 阅读