Skip to main content

108. Convert Sorted Array to Binary Search Tree

解题思路​

这道题的目标是将一个有序数组转换成一个高度平衡的二叉搜索树 (BST)。在 BST 中，左子树的所有节点都小于根节点，而右子树的所有节点都大于根节点。

为了使 BST 高度平衡，我们应选择数组的中间元素作为根节点，然后递归构造左右子树：

  1. 选择数组的中间元素 作为根节点，这样左右子树的高度尽量接近。
  2. 递归构造左子树，使用左半部分的元素。
  3. 递归构造右子树，使用右半部分的元素。
  4. 递归终止条件：当 left > right 时，返回 None。

Python 代码​

from typing import List, Optional

# 定义二叉树节点
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 helper(left: int, right: int) -> Optional[TreeNode]:
            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 preorder_traversal(root):
    """前序遍历输出二叉树"""
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right) if root else []

nums = [-10, -3, 0, 5, 9]
solution = Solution()
tree = solution.sortedArrayToBST(nums)

print(preorder_traversal(tree))  # 可能的输出: [0, -3, -10, 9, 5]

复杂度分析​

  • 时间复杂度：O(N)，每个元素都被访问一次并创建一个节点。
  • 空间复杂度：O(log N)，递归调用栈的深度在平衡 BST 中大约为 log N。

示例分析​

输入：​

nums = [-10, -3, 0, 5, 9]

执行步骤：​

  1. 选择 0 作为根节点。
  2. 左子树从 [-10, -3] 递归构造：
    • 选择 -3 作为左子树根。
    • -10 作为 -3 的左子节点。
  3. 右子树从 [5, 9] 递归构造：
    • 选择 9 作为右子树根。
    • 5 作为 9 的左子节点。

输出 (BST 结构)：​

      0
     / \
   -3   9
   /   /
 -10   5

前序遍历输出：​

[0, -3, -10, 9, 5]

总结​

  • 选择中间元素作为根，确保平衡性。
  • 递归构建左右子树。
  • 时间复杂度 O(N)，空间复杂度 O(log N)。

这样，我们就能高效地将一个有序数组转换成平衡二叉搜索树！🚀