https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树（BST）。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
附：此题提交时必须注释掉class TreeNode类
法一：中序遍历，总是选择中间位置左边的数字作为根节点
我要评论
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def helper(left, right):
if left > right:
return None
# 总是选择中间位置左边的数字作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1) # 写成helper返回
时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。
空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。
二叉搜索树的中序遍历结果为递增序列。现在题目给了我们一个递增序列，要求我们构造一棵二叉搜索树，就是要实现这一特性的逆过程。
中序遍历的顺序为：左节点 → 根节点 → 右节点。
构造一棵树的过程可以拆分成无数个这样的子问题：构造树的每个节点以及节点之间的关系。对于每个节点来说，都需要：
要求构造一棵「高度平衡」的树，所以我们在选取节点时选择数组的中点作为根节点，以此来保证平衡性。
法一类似写法（没写helper函数）
# 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):
if not nums:
return None
# 找到中点作为根节点
mid = len(nums) // 2
node = TreeNode(nums[mid])
# 左侧数组作为左子树
left = nums[:mid]
right = nums[mid+1:]
# 递归调用
node.left = self.sortedArrayToBST(left)
node.right = self.sortedArrayToBST(right)
return node
本文地址：https://blog.csdn.net/IOT_victor/article/details/107111399
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
荐 python知识点：函数参数、迭代器、生成器、装饰器、函数式变成、map/reduce、filter、sorted、继承和多态
qt designer 关于多页面跳转之后同一个页面出现多次的问题
网友评论