二叉树题解——将有序数组转换为二叉搜索树【LeetCode】传统解法

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

方法一：中序遍历，总是选择中间位置左边的数字作为根节点

选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/2，此处的除法为整数除法。

1.1 核心思想

• 分治法：将数组分成左右两部分，递归构建左子树和右子树。
• 高度平衡：通过选择数组的中间元素作为根节点，确保左右子树的节点数尽可能相等，从而保证树的高度平衡。

1.2 具体步骤

1. 递归终止条件：如果左边界 left 大于右边界 right，说明当前子数组为空，返回 None。
2. 选择根节点：
   • 计算中间位置 mid = (left + right) // 2。
   • 将 nums[mid] 作为根节点的值。
3. 递归构建子树：
   • 左子树的范围是 [left, mid - 1]，递归调用 helper 构建左子树。
   • 右子树的范围是 [mid + 1, right]，递归调用 helper 构建右子树。
4. 返回根节点：将构建好的根节点返回。

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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)

示例 1：

输入：nums = [-10, -3, 0, 5, 9]

• 初始调用：helper(0, 4)。
  • mid = (0 + 4) // 2 = 2，根节点为 0。
  • 左子树范围 [0, 1]，右子树范围 [3, 4]。
• 递归调用 helper(0, 1)：
  • mid = (0 + 1) // 2 = 0，根节点为 -10。
  • 左子树范围 [0, -1]（返回 None），右子树范围 [1, 1]。
• 递归调用 helper(1, 1)：
  • mid = (1 + 1) // 2 = 1，根节点为 -3。
  • 左子树范围 [1, 0]（返回 None），右子树范围 [2, 1]（返回 None）。
• 递归调用 helper(3, 4)：
  • mid = (3 + 4) // 2 = 3，根节点为 5。
  • 左子树范围 [3, 2]（返回 None），右子树范围 [4, 4]。
• 递归调用 helper(4, 4)：
  • mid = (4 + 4) // 2 = 4，根节点为 9。
  • 左子树范围 [4, 3]（返回 None），右子树范围 [5, 4]（返回 None）。
• 最终返回的 BST 结构如下：

       0
      / \
    -10  5
      \   \
      -3   9

方法二：中序遍历，总是选择中间位置右边的数字作为根节点

选择中间位置右边的数字作为根节点，则根节点的下标为 mid=(left+right+1)/2，此处的除法为整数除法。

方法三：中序遍历，选择任意一个中间位置数字作为根节点

选择任意一个中间位置数字作为根节点，则根节点的下标为 mid=(left+right)/2 和 mid=(left+right+1)/2 两者中随机选择一个，此处的除法为整数除法。

1.1 核心思想

• 分治法：将数组分成左右两部分，递归构建左子树和右子树。
• 随机化策略：在选择中间元素时，随机决定是选择中间位置左边的元素还是右边的元素，从而生成不同的 BST。

1.2 具体步骤

1. 递归终止条件：
   • 如果左边界 left 大于右边界 right，说明当前子数组为空，返回 None。
2. 选择根节点：
   • 计算中间位置 mid = (left + right + randint(0, 1)) // 2。
     • randint(0, 1) 随机返回 0 或 1，从而决定 mid 是偏向左边还是右边。
   • 将 nums[mid] 作为根节点的值。
3. 递归构建子树：
   • 左子树的范围是 [left, mid - 1]，递归调用 helper 构建左子树。
   • 右子树的范围是 [mid + 1, right]，递归调用 helper 构建右子树。
4. 返回根节点：
   • 将构建好的根节点返回。

from random import randint  # 导入 randint 函数

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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 + randint(0, 1)) // 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)