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

张开发
• 2026/4/10 4:33:42 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

leetc0de 108. 将有序数组转换为二叉搜索树
什么是“二叉搜索树 (BST)”二叉搜索树Binary Search Tree有一个绝对铁律左小、右大。 对于树上的任何一个节点它的左子树里所有的值都必须小于这个节点的值。它的右子树里所有的值都必须大于这个节点的值。“平衡”的定义:一棵平衡二叉树规定任何一个节点的左子树和右子树的深度高度差绝对不能超过 1。做题思路如何把升序数组变成平衡二叉搜索树题目给的是一个已经排好序的数组比如[-10, -3, 0, 5, 9]。 既然要保证“平衡”左右两边节点数量差不多又要保证“左小右大”我们该选谁当这棵树的根节点答案呼之欲出选最中间的那个数核心思路分治法 / 递归找中点当老大取数组最中间的元素比如这里的0作为根节点。这样根节点左边的数全比它小右边的数全比它大且左右两边的数量绝对均等或只差一个。左半边建左子树拿中点左边的数组段[-10, -3]继续重复第一步把它的中点变成0的左孩子。右半边建右子树拿中点右边的数组段[5, 9]继续重复第一步把它的中点变成0的右孩子。何时结束当切分出的数组段为空没有元素了时说明到底了返回空节点None。这个不断“找中间、分两头”的过程其实就相当于把你平时查字典时用的二分查找法实体化成了一棵看得见摸得着的树# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None length len(nums)//2 left_tree self.sortedArrayToBST(nums[0:length]) right_tree self.sortedArrayToBST(nums[length1:]) root TreeNode(nums[length],left_tree,right_tree) return root

更多文章