# 如何将有序数组转换为二叉搜索树
## 引言
二叉搜索树（Binary Search Tree, BST）是一种常见的数据结构，它具有以下重要特性：
- 左子树所有节点值小于根节点值
- 右子树所有节点值大于根节点值
- 左右子树也分别是二叉搜索树
当给定一个**有序数组**时，如何高效地将其转换为高度平衡的二叉搜索树？本文将深入探讨这个问题，提供多种解决方案，并分析其时间复杂度和空间复杂度。
## 问题定义
给定一个按升序排列的整数数组 `nums`，将其转换为满足以下条件的二叉搜索树：
1. 树高度平衡（左右子树高度差不超过1）
2. 保持二叉搜索树的性质
示例：
```python
输入: [-10, -3, 0, 5, 9]
输出:
0
/ \
-3 9
/ /
-10 5
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sortedArrayToBST(nums):
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)
def sortedArrayToBST(nums):
if not nums:
return None
stack = []
root = TreeNode()
stack.append((0, len(nums) - 1, root, 'left'))
while stack:
left, right, parent, direction = stack.pop()
mid = (left + right) // 2
if direction == 'left':
parent.left = TreeNode(nums[mid])
node = parent.left
else:
parent.right = TreeNode(nums[mid])
node = parent.right
if left <= mid - 1:
stack.append((left, mid - 1, node, 'left'))
if mid + 1 <= right:
stack.append((mid + 1, right, node, 'right'))
return root.left
def sortedArrayToBST(nums):
def count_nodes(left, right):
if left > right:
return 0
return 1 + count_nodes(left, (left+right)//2 - 1) + count_nodes((left+right)//2 + 1, right)
n = len(nums)
root = TreeNode()
stack = [(0, n - 1, root)]
idx = 0
while stack:
left, right, node = stack.pop()
mid = (left + right) // 2
# In-order traversal processing
if left <= mid - 1:
node.left = TreeNode()
stack.append((left, mid - 1, node.left))
node.val = nums[idx]
idx += 1
if mid + 1 <= right:
node.right = TreeNode()
stack.append((mid + 1, right, node.right))
return root
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 递归 | O(n) | O(log n) | 代码简洁 | 递归栈可能溢出 |
| 迭代 | O(n) | O(n) | 避免递归 | 实现较复杂 |
| 中序模拟 | O(n) | O(n) | 理论价值高 | 实现最复杂 |
空数组输入：
if not nums:
return None
单元素数组：
if len(nums) == 1:
return TreeNode(nums[0])
大数组处理：
如何处理有重复元素的数组？
如何优化为AVL树或红黑树？
如何支持动态插入/删除？
将有序数组转换为平衡二叉搜索树是一个经典的算法问题，其核心在于： 1. 利用数组的有序性对应BST的中序遍历 2. 通过分治法保证树的平衡性 3. 递归是最直观的解决方案，迭代法则更适合处理大数据量
理解这个问题不仅有助于掌握BST的特性，也是学习分治算法和树操作的绝佳案例。
”`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
