算法第五十四题：将有序数组转换为二叉搜索树，递归，Leetcode编号108，难度简单

2023-03-26 08:33| 来源: 网络整理| 查看: 265

题目：

解法：递归

思路：

二叉搜索树是一种常见的二叉树结构，其中左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。

给出 nums，和左右指针，在左右指针之间数组，我们需要在其中找到一个节点作为根节点，将数组分为左右两个子数组，分别递归构建左子树和右子树，并将这两个子树挂在根节点上。

对于搜索树而言，自然是选择中间的节点作为根节点。

递归的边界条件：

当数组为空，返回None当数组只有一个元素时，返回这个元素构成的节点。# time: O(n) # space: O(logn) # 执行用时：56 ms, 在所有 Python3 提交中击败了10.50%的用户 # 内存消耗：16.4 MB, 在所有 Python3 提交中击败了61.09%的用户 # 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]: def buildTree(nums, left, right): if left > right: # 空数组 return None if left == right: # 只有一个数 return TreeNode(nums[left]) mid = (left+right)//2 # 选择根节点的val root = TreeNode(nums[mid]) root.left = buildTree(nums, left, mid-1) # 构建左子树 root.right = buildTree(nums, mid+1, right) # 构建右子树 return root return buildTree(nums, 0, len(nums)-1)

同名公众号：舟晓南

对机器学习，深度学习，python，算法题感兴趣，欢迎关注专栏，学习笔记已原创100+篇，持续更新中~ ^_^

专栏文章举例：

【机器学习】关于逻辑斯蒂回归，看这一篇就够了！解答绝大部分关于逻辑斯蒂回归的常见问题，以及代码实现 - 知乎 (zhihu.com)

【机器学习】朴素贝叶斯 -> 半朴素贝叶斯 -> 贝叶斯网络 -> 贝叶斯优化，看这一篇就够了！ - 知乎 (zhihu.com)

关于K近邻（KNN），看这一篇就够了！算法原理，kd树，球树，KNN解决样本不平衡，剪辑法，压缩近邻法 - 知乎 (zhihu.com)

专栏文章举例：

记录一下工作中用到的少有人知的pandas骚操作，提升工作效率 - 知乎 (zhihu.com)

关于切片时不考虑最后一个元素以及为什么从0开始计数的问题 - 知乎 (zhihu.com)

专栏文章举例：

算法第二十题：最长回文子串，动态规划|中心扩散法，Leetcode编号5，难度中等，字符串题 - 知乎 (zhihu.com)

算法第二十一题： Z字形变换，震荡指针，Leetcode编号6，难度中等，字符串题 - 知乎 (zhihu.com)

算法第九题：四数之和，排序暴力+排序双指针，Leetcode编号18，难度中等 - 知乎 (zhihu.com)

关于转行：

舟晓南：如何转行和学习数据分析 | 工科生三个月成功转行数据分析心得浅谈

舟晓南：求职数据分析师岗位，简历应该如何写？｜工科生三个月成功转行数据分析心得浅谈

我建了个数据分析，机器学习，深度学习的群~ 需要学习资料，想要加入社群均可私信~

在群里我会不定期分享各种数据分析相关资源，技能学习技巧和经验等等~

详情私信，一起进步吧！

写于上海 2023-03-23

【本文地址】

公司简介

联系我们